# More on the sum-freedom of the multiplicative inverse function

Claude Carlet  Department of Mathematics, University Paris 8, 93526 Saint-
Denis France and Department of Informatics, University of Bergen, 5005 Bergen
Norway<EMAIL_ADDRESS>and  Xiang-dong Hou  Department of Mathematics
and Statistics, University of South Florida, Tampa, FL 33620<EMAIL_ADDRESS>
###### Abstract.

In two papers entitled “Two generalizations of almost perfect nonlinearity”
and “On the vector subspaces of $\mathbb{F}_{2^{n}}$ over which the
multiplicative inverse function sums to zero”, the first author has introduced
and studied the notion of sum-freedom of vectorial functions, which expresses
that a function sums to nonzero values over all affine subspaces of
$\mathbb{F}_{2^{n}}$ of a given dimension $k\geq 2$, and he then focused on
the $k$th order sum-freedom of the multiplicative inverse function
$x\in\mathbb{F}_{2^{n}}\mapsto x^{2^{n}-2}$. Some general results were given
for this function (in particular, the case of affine spaces that do not
contain 0 was solved positively), and the cases of $k\in\\{3,n-3\\}$ and of
$k$ not co-prime with $n$ were solved as well (negatively); but the cases of
those linear subspaces of dimension $k\in\llbracket 4;n-4\rrbracket$, co-prime
with $n$, were left open. The present paper is a continuation of the previous
work. After studying, from two different angles, the particular case of those
linear subspaces that are stable under the Frobenius automorphism, we deduce
from the second approach that, for $k$ small enough (approximately, $3\leq
k\leq n/10$), the multiplicative inverse function is not $k$th order sum-free.
Finally, we extend a result previously obtained in the second paper mentioned
above, and we deduce in particular that, for any even $n$ and every $2\leq
k\leq n-2$, the multiplicative inverse function is not $k$th order sum-free.

###### Key words and phrases:

APN function, finite field, Lang-Weil bound, multiplicative inverse function,
sum-free function,

###### 2020 Mathematics Subject Classification:

11G25, 11T06, 11T71, 94D10

* Claude Carlet was partially supported by the Norwegian Research Council.

##  1\. A Brief Introduction

Let $n$ and $k$ be positive integers such that $1\leq k\leq n-1$. A (so-called
vectorial) function $F:\mathbb{F}_{2^{n}}\to\mathbb{F}_{2^{n}}$ is said to be
$k$th order sum-free if, for every $k$-dimensional affine subspace $A$ of
$\mathbb{F}_{2^{n}}$,

(1.1) $\sum_{x\in A}F(x)\neq 0.$

For $k=1$, this corresponds to the bijectivity of $F$, and we shall then
assume $k\geq 2$. For $k=2$, it corresponds to almost perfect nonlinearity
[18].

Let $F_{\text{\rm inv}}:\mathbb{F}_{2^{n}}\to\mathbb{F}_{2^{n}}$ be defined by

$F_{\text{\rm inv}}(x)=x^{2^{n}-2}=\begin{cases}x^{-1}&\text{if}\ x\neq 0,\cr
0&\text{if}\ x=0.\end{cases}$

We know from Nyberg [18] that $F_{\text{\rm inv}}$ is second order sum-free if
and only if $n$ is odd. It is also known ([3]) that if $A$ is an affine
subspace of $\mathbb{F}_{2^{n}}$ not containing $0$, then $\sum_{x\in
A}F_{\text{\rm inv}}(x)\neq 0$, because

$\sum_{u\in A}\frac{1}{u}=\frac{\prod_{0\neq u\in E}u}{\prod_{u\in A}u},$

where $E$ is the linear subspace of $\mathbb{F}_{2^{n}}$ such that $A$ is a
coset of $E$. Therefore, $F_{\text{\rm inv}}$ is not $k$th order sum-free if
and only if there is a $k$-dimensional linear subspace $E$ of
$\mathbb{F}_{2^{n}}$ such that

(1.2) $\sum_{0\neq x\in E}\frac{1}{x}=0.$

Let us summarize the values of $k\geq 3$ for which the $k$th order sum-freedom
of $F_{\text{\rm inv}}$ could be deduced in [3, 4] (in some cases from more
general results):

  * •

If $\text{gcd}(k,n)>1$, $F_{\text{\rm inv}}$ is not $k$th order sum-free,

  * •

$F_{\text{\rm inv}}$ is $k$th order sum-free if and only if it is $(n-k)$th
order sum-free,

  * •

If $6\mid n$, then $F_{\text{\rm inv}}$ is not $k$th order sum-free for $2\leq
k\leq n-2$,

  * •

For $n\geq 6$, $F_{\text{\rm inv}}$ is not $3$rd order sum-free,

  * •

For even $n\geq 6$, $F_{\text{\rm inv}}$ is not $4$th order sum-free.

The above results and computer investigations suggest that the sum-freedom of
$F_{\text{\rm inv}}$ follows a simple pattern as stated in the following
conjecture.

######  Conjecture 1.1.

[4] For even $n$, $F_{\text{\rm inv}}$ is not $k$th order sum-free for $2\leq
k\leq n-2$. For odd $n$, $F_{\text{\rm inv}}$ is not $k$th order sum-free for
$3\leq k\leq n-3$.

The conjecture has been confirmed for $n\leq 12$ [4] and for $6\mid n$ (as
indicated above). In the present paper, we prove several new results
concerning this conjecture. We find that, if $X^{n}+1$ has a factor of the
form $X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}\in\mathbb{F}_{2}[X]$, then
$F_{\text{\rm inv}}$ is not $k$th order sum-free. Using the Lang-Weil bound on
the number of zeros of absolute irreducible polynomials over finite fields, we
prove that $F_{\text{\rm inv}}$ is not $k$th order sum-free when $k\geq 3$ and
$n\geq 10.8k-5$. We are also able to show that Conjecture 1.1 holds for all
even $n$ by extending a result in [4].

The rest of the paper is organized as follows: In Section 2, we study the
companion matrix of the subspace polynomial of a $k$-dimensional subspace of
$\mathbb{F}_{2^{n}}$. This leads to the conclusion that, if $X^{n}+1$ has a
factor of the form
$X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}\in\mathbb{F}_{2}[X]$, then
$F_{\text{\rm inv}}$ is not $k$th order sum-free. We then describe the values
of $k$ so that such a factor exists. Section 3 provides an alternative
approach to Section 2 based on the Moore determinant. Not only does this new
approach lead us to the same results of Section 2, but also it prepares us for
the discussion in the next section. In Section 4, using the Lang-Weil bound,
we show that when $k\geq 3$ and $n\geq 10.8k-5$, $F_{\text{\rm inv}}$ is not
$k$th order sum-free. The final section contains a short proof for Conjecture
1.1 with even $n$.

##  2\. Case of affine subspaces (globally) invariant under the Frobenius
automorphism

###  2.1. A companion matrix approach

We know (see e.g. [6, 16]) that a linearized polynomial
$\sum_{i=0}^{k}b_{i}X^{2^{i}}\in\mathbb{F}_{2^{n}}[X]$ with $b_{k}=1$ has
$2^{k}$ distinct zeros in $\mathbb{F}_{2^{n}}$, that is, equals a so-called
subspace polynomial $L_{E_{k}}(X):=\prod_{u\in E_{k}}(X+u)$, for some
$k$-dimensional linear subspace $E_{k}$ of $\mathbb{F}_{2^{n}}$, if and only
if the so-called companion matrix

(2.1) $A=\left[\begin{array}[]{cccccc}0&0&0&\ldots&0&b_{0}\\\
1&0&0&\ldots&0&b_{1}\\\ 0&1&0&\ldots&0&b_{2}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&0&\ldots&1&b_{k-1}\\\
\end{array}\right].$

satisfies $AA^{[2]}\cdots A^{[2^{n-1}]}=I_{k}$, where $A^{[2^{i}]}$ is the
matrix obtained from $A$ by applying to each of its entries the automorphism
$x\mapsto x^{2^{i}}$, and where $I_{k}$ is the $k\times k$ identity matrix. It
is proved in [4] that we have $\sum_{x\in E_{k}}F_{\text{\rm inv}}(x)=0$ if
and only if $b_{1}=0$. We are then looking at whether such matrices $A$ exist
such that $b_{1}=0$.

Remark. Necessarily, we have $b_{0}=\prod_{u\in E_{k},u\neq 0}u\neq 0$. If
$\gcd(k,n)=1$, then $2^{k}-1$ is invertible modulo $2^{n}-1$, and we can
assume without loss of generality that $b_{0}=1$, because by dividing each
element $u$ of $E_{k}$ by $b_{0}^{1/(2^{k}-1)}$, we change $b_{0}$ into 1.

The polynomial $L_{E_{k}}(X)$ has all its coefficients $b_{i}$ in
$\mathbb{F}_{2}$ if and only if $L_{E_{k}}(X^{2})=(L_{E_{k}}(X))^{2}$, that
is, $E_{k}$ is stable under the Frobenius automorphism. Then, the condition
$AA^{[2]}\cdots A^{[2^{n-1}]}=I_{k}$ becomes $A^{n}=I_{k}$.

Remark. If $k$ divides $n$, the linearized polynomial $X^{2^{k}}+X$ satisfies
the condition $A^{n}=I_{k}$ (as expected since $X^{2^{k}}+X$ is the subspace
polynomial corresponding to the vector space $\mathbb{F}_{2^{k}}$), because
$A$ is then the matrix of the shift over $\mathbb{F}_{2^{n}}^{k}$ and it
satisfies $A^{n}=I_{k}$, thanks to the fact that $k$ divides $n$. This is also
coherent with the fact that $F_{\text{\rm inv}}$ sums to 0 over
$\mathbb{F}_{2^{k}}$ since it is a permutation of this field.

For general $k$ and $n$, recall that the Cayley-Hamilton theorem states that
the characteristic equation of $A$, $\det(\lambda I-A)=0$ (where $\det$ is the
determinant operation and $\lambda$ is a scalar variable), is satisfied when
we replace $\lambda$ by the matrix $A$ itself (obtaining then a matrix
relation), and it writes $A^{k}=\sum_{i=0}^{k-1}b_{i}A^{i}$ (see e.g. [8,
pages 146-147] or https://en.wikipedia.org/wiki/Companion_matrix). The order
of the matrix $A$ equals the order of the polynomial
$P(X)=\sum_{i=0}^{k}b_{i}X^{i}$ (see e.g. [7]). We then have

######  Theorem 2.1.

Let $L(X)=\sum_{i=0}^{k}b_{i}X^{2^{i}}$ (with $b_{k}=1$) be a linearized
polynomial with all its coefficients in $\mathbb{F}_{2}$. Then $L(X)$ splits
completely over $\mathbb{F}_{2^{n}}$ and has simple zeros (i.e. equals
$L_{E_{k}}(X)$ for some $k$-dimensional subspace $E_{k}$ of
$\mathbb{F}_{2^{n}}$) if and only if the matrix $A$ defined in (2.1) satisfies
$A^{n}=I_{k}$. This is equivalent to the condition that the polynomial
$P(X)=\sum_{i=0}^{k}b_{i}X^{i}\in\mathbb{F}_{2}[X]$ divides $X^{n}+1$. Hence,
if $X^{n}+1$ has a factor
$X^{k}+a_{k-1}X^{k-1}+\dots+a_{2}X^{2}+a_{0}\in\mathbb{F}_{2}[X]$, then
$F_{\text{\rm inv}}$ is not $k$th order sum-free.

Note that the coefficient of $X^{2}$ in $\sum_{i=0}^{k}b_{i}X^{2^{i}}$ equals
that of $X$ in $\sum_{i=0}^{k}b_{i}X^{i}$. From Theorem 2.1, we deduce the
following corollary which gives for each (composite) $n$ a set of values of
$k$ for which $F_{\text{\rm inv}}$ is not $k$th order sum-free.

######  Corollary 2.2.

Let $\prod_{i=1}^{l}p_{i}^{\alpha_{i}}$ be the prime factorization of $n$. For
every choice of the binary hyper-matrix

$\epsilon=(\epsilon_{j_{1},\dots,j_{l}})_{(j_{1},\dots,j_{l})\in\prod_{i=1}^{l}\\{0,\dots,\alpha_{i}\\}},$

(with $\epsilon_{j_{1},\dots,j_{l}}\in\\{0,1\\}\subset\mathbb{Z}$) such that
the integer

(2.2) $\sum_{(j_{1},\dots,j_{l})\in\\{0,1\\}^{l}}\epsilon_{j_{1},\dots,j_{l}}$

is even (possibly 0), the multiplicative inverse function $F_{\text{\rm inv}}$
over $\mathbb{F}_{2^{n}}$ is not $k$th order sum-free with

$k=\sum_{(j_{1},\dots,j_{l})\in\prod_{i=1}^{l}\\{0,\dots,\alpha_{i}\\}}\epsilon_{j_{1},\dots,j_{l}}\,\prod_{i\in\\{1,\dots,l\\}\atop
j_{i}\geq 1}(p_{i}-1)\,p_{i}^{j_{i}-1}.$

###### Proof.

For each value of $\epsilon$, let us consider the set that we shall denote by
$D_{\epsilon}$, of those (distinct) divisors of $n$ equal to
$\prod_{i=1}^{l}p_{i}^{j_{i}}$, where $\epsilon_{j_{1},\dots,j_{l}}=1$. We
consider then the cyclotomic polynomials (see e.g. [12]) whose indices equal
these divisors. Recall that the cyclotomic polynomial of index 1 equals $X-1$
(that is, $X+1$ in characteristic 2), and the cyclotomic polynomial of index
$p_{i}$ equals
$\Phi_{p_{i}}(X)=(X^{p_{i}}-1)/(X-1)=1+X+X^{2}+\dots+X^{p_{i}-1}$. For $j\geq
1$, the cyclotomic polynomial of index $p_{i}^{j}$ equals
$\Phi_{p_{i}^{j}}(X)=\Phi_{p_{i}}(X^{p_{i}^{j-1}})$ and has then degree
$(p_{i}-1)\,p_{i}^{j-1}$. The cyclotomic polynomials of indices all the
divisors of $n$ are obtained by iteratively applying the formula
$\Phi_{p_{i}^{j}r}(X)=\Phi_{p_{i}r}(X^{p_{i}^{j-1}})=\Phi_{r}(X^{p_{i}^{j}})/\Phi_{r}(X^{p_{i}^{j-1}})$,
which is valid when $j\geq 1$ and $\gcd(p_{i},r)=1$. The degree of
$\Phi_{p_{i}^{j}r}(X)$ equals then
$(p_{i}^{j}-p_{i}^{j-1})\deg(\Phi_{r})=(p_{i}-1)p_{i}^{j-1}\deg(\Phi_{r})$.
The coefficient of $X$ in $\Phi_{p_{i}^{j}r}(X)$ equals the value at 0, for
$j\geq 1$, of the polynomial derivative of the fraction
$\Phi_{r}(X^{p_{i}^{j}})/\Phi_{r}(X^{p_{i}^{j-1}})$, that is,

$\frac{\Phi_{r}(0)\Phi^{\prime}_{r}(0)p_{i}^{j-1}0^{p_{i}^{j-1}-1}}{(\Phi_{r}(0))^{2}},$

which equals $\Phi^{\prime}_{r}(0)$ if $j=1$ and 0 otherwise. Then, we have
$\Phi_{p_{i}^{j}r}(X)\equiv 1+X\pmod{X^{2}}$ if $\Phi_{r}(X)\equiv
1+X\pmod{X^{2}}$ and $j\in\\{0,1\\}$, and $\Phi_{p_{i}^{j}r}(X)\equiv
1\pmod{X^{2}}$ otherwise. Hence, we have $\Phi_{p_{1}^{s_{1}}\cdots
p_{l}^{s_{l}}}(X)\equiv 1+X\pmod{X^{2}}$ if $s_{i}\in\\{0,1\\}$ for all
$i\in\\{1,\dots,l\\}$, and $\Phi_{p_{1}^{s_{1}}\cdots p_{l}^{s_{l}}}(X)\equiv
1\pmod{X^{2}}$ otherwise. We have $X^{n}+1=\prod_{d\mid n}\Phi_{d}(X)$. Then,
the product $\prod_{d\in D_{\epsilon}}\Phi_{d}$ being a product of cyclotomic
polynomials $\Phi_{d}$ such that all $d\in D_{\epsilon}$ are distinct, it
divides $X^{n}+1$. We complete the proof by combining Theorem 2.1 and the fact
that $\sum_{u\in E,u\neq 0}1/u$ is equal to 0 if and only if the coefficient
of $X^{2}$ in the linearized polynomial $L_{E}(X)=\prod_{u\in E}(X+u)$ equals
0. (Note that the condition that (2.2) is even means that the coefficient of
$X$ in $\prod_{d\in D_{\epsilon}}(X)$ equals 0.) ∎

Note that

$\sum_{(j_{1},\dots,j_{l})\in\prod_{i=1}^{l}\\{0,\dots,\alpha_{i}\\}}\epsilon_{j_{1},\dots,j_{l}}\,\prod_{i\in\\{1,\dots,l\\}\atop
j_{i}\geq 1}(p_{i}-1)\,p_{i}^{j_{i}-1}$

may be co-prime with $n$, and this corollary covers values of $k$ that are not
covered by [3, 4]. It covers in fact many values of $k$ for each $n$ (which
needs to be composite, though), all the more when it has many prime divisors
at large powers.

Example. Take $n=12$. We have $p_{1}=2,p_{2}=3$, $\alpha_{1}=2,\alpha_{2}=1$.
Since $l=2$, each $\epsilon$ is a matrix, and we shall choose $j_{1}$ as row-
index (which makes three rows) and $j_{2}$ as column-index (which makes two
columns). The values of the matrix $\epsilon$ satisfying the condition in
Corollary 2.2 are displayed below, as the first term of each triple. The
corresponding set $D_{\epsilon}$ of distinct divisors of $n$ (that we list in
the order obtained by visiting each position equal to 1 in the first column,
and then in the second column) is the second term, and the corresponding value
of $k$ is the third term.

$(\epsilon,D_{\epsilon},k)=$ $\left(\left[\begin{array}[]{l}10\\\ 10\\\
00\end{array}\right],\\{1,2\\},2\right),\left(\left[\begin{array}[]{l}11\\\
00\\\
00\end{array}\right],\\{1,3\\},3\right),\left(\left[\begin{array}[]{l}10\\\
01\\\ 00\end{array}\right],\\{1,6\\},3\right),$
$\left(\left[\begin{array}[]{l}01\\\ 10\\\
00\end{array}\right],\\{2,3\\},3\right),\left(\left[\begin{array}[]{l}01\\\
01\\\
00\end{array}\right],\\{3,6\\},4\right),\left(\left[\begin{array}[]{l}00\\\
11\\\ 00\end{array}\right],\\{2,6\\},3\right),$
$\left(\left[\begin{array}[]{l}01\\\ 10\\\
10\end{array}\right],\\{2,4,3\\},5\right),\left(\left[\begin{array}[]{l}01\\\
01\\\
10\end{array}\right],\\{4,3,6\\},6\right),\left(\left[\begin{array}[]{l}00\\\
11\\\ 10\end{array}\right],\\{2,4,6\\},5\right),$
$\left(\left[\begin{array}[]{l}10\\\ 10\\\
10\end{array}\right],\\{1,2,4\\},4\right),\left(\left[\begin{array}[]{l}11\\\
00\\\
10\end{array}\right],\\{1,4,3\\},5\right),\left(\left[\begin{array}[]{l}10\\\
01\\\ 10\end{array}\right],\\{1,4,6\\},5\right),$
$\left(\left[\begin{array}[]{l}01\\\ 10\\\
01\end{array}\right],\\{2,3,12\\},7\right),\left(\left[\begin{array}[]{l}01\\\
01\\\
01\end{array}\right],\\{3,6,12\\},8\right),\left(\left[\begin{array}[]{l}00\\\
11\\\ 01\end{array}\right],\\{2,6,12\\},7\right),$
$\left(\left[\begin{array}[]{l}10\\\ 10\\\
01\end{array}\right],\\{1,2,12\\},6\right),\left(\left[\begin{array}[]{l}11\\\
00\\\
01\end{array}\right],\\{1,3,12\\},7\right),\left(\left[\begin{array}[]{l}10\\\
01\\\ 01\end{array}\right],\\{1,6,12\\},7\right),$
$\left(\left[\\!\begin{array}[]{l}01\\\ 10\\\
11\end{array}\\!\right],\\{2,4,3,12\\},9\right),\left(\left[\\!\begin{array}[]{l}01\\\
01\\\
11\end{array}\\!\right],\\{4,3,6,12\\},10\right),\left(\left[\\!\begin{array}[]{l}00\\\
11\\\ 11\end{array}\\!\right],\\{2,4,6,12\\},9\right),$
$\left(\left[\begin{array}[]{l}10\\\ 10\\\
11\end{array}\right],\\{1,2,4,12\\},8\right),\left(\left[\begin{array}[]{l}11\\\
00\\\
11\end{array}\right],\\{1,4,3,12\\},9\right),\left(\left[\begin{array}[]{l}10\\\
01\\\ 11\end{array}\right],\\{1,4,6,12\\},9\right).$

Hence, Corollary 2.2 implies that the multiplicative inverse function over
$\mathbb{F}_{2^{12}}$ is not $k$th-order-sum-free where
$k\in\\{2,3,4,5,6,7,8,9,10\\}$.

Other examples.
\- For $n=6$, we have $p_{1}=2,p_{2}=3$, $\alpha_{1}=1,\alpha_{2}=1$, and

$(\epsilon,D_{\epsilon},k)=$ $\left(\left[\begin{array}[]{l}01\\\
10\end{array}\right],\\{2,3\\},3\right),\left(\left[\begin{array}[]{l}01\\\
01\end{array}\right],\\{3,6\\},4\right),\left(\left[\begin{array}[]{l}00\\\
11\end{array}\right],\\{2,6\\},3\right),$ $\left(\left[\begin{array}[]{l}10\\\
10\end{array}\right],\\{1,2\\},2\right),\left(\left[\begin{array}[]{l}11\\\
00\end{array}\right],\\{1,3\\},3\right),\left(\left[\begin{array}[]{l}10\\\
01\end{array}\right],\\{1,6\\},3\right);$

\- for $n=8$,

$(\epsilon,D_{\epsilon},k)=$ $\left(\left[\begin{array}[]{l}0\\\ 0\\\ 1\\\
0\end{array}\right],\\{4\\},2\right),\left(\left[\begin{array}[]{l}1\\\ 1\\\
0\\\ 0\end{array}\right],\\{1,2\\},2\right),\left(\left[\begin{array}[]{l}1\\\
1\\\ 1\\\ 0\end{array}\right],\\{1,2,4\\},4\right),$
$\left(\left[\begin{array}[]{l}0\\\ 0\\\ 1\\\
1\end{array}\right],\\{4,8\\},6\right),\left(\left[\begin{array}[]{l}1\\\ 1\\\
0\\\
1\end{array}\right],\\{1,2,8\\},6\right),\left(\left[\begin{array}[]{l}1\\\
1\\\ 1\\\ 1\end{array}\right],\\{1,2,4,8\\},8\right);$

\- for $n=9$,

$(\epsilon,D_{\epsilon},k)=\left(\left[\begin{array}[]{l}0\\\ 0\\\
1\end{array}\right],\\{9\\},6\right),\left(\left[\begin{array}[]{l}1\\\ 1\\\
0\end{array}\right],\\{1,3\\},3\right),\left(\left[\begin{array}[]{l}1\\\ 1\\\
1\end{array}\right],\\{1,3,9\\},9\right);$

\- for $n=10$, we have $p_{1}=2,p_{2}=5$, $\alpha_{1}=1,\alpha_{2}=1$, and

$(\epsilon,D_{\epsilon},k)=$ $\left(\left[\begin{array}[]{l}01\\\
10\end{array}\right],\\{2,5\\},5\right),\left(\left[\begin{array}[]{l}01\\\
01\end{array}\right],\\{5,10\\},8\right),\left(\left[\begin{array}[]{l}00\\\
11\end{array}\right],\\{2,10\\},5\right),$
$\left(\left[\begin{array}[]{l}10\\\
10\end{array}\right],\\{1,2\\},2\right),\left(\left[\begin{array}[]{l}11\\\
00\end{array}\right],\\{1,5\\},5\right),\left(\left[\begin{array}[]{l}10\\\
01\end{array}\right],\\{1,10\\},5\right).$

Similarly, for $n=15$, the set of values of $k$ given by Corollary 2.2 is
$\\{3,4,\dots,12,15\\}$, and for $n=21$, it is $\\{3,4,\dots,18,21\\}$.

The following corollary gives an infinite class of values of $(k,n)$ such that
the multiplicative inverse $(n,n)$-function is not $k$th order sum-free.

######  Corollary 2.3.

If $n$ is divisible by an integer $s\geq 2$ and if $r\leq n/s$ is the degree
of any divisor of $X^{n/s}+1$ in $\mathbb{F}_{2}[X]$, then the multiplicative
inverse function is not $(sr)$th order sum-free.

###### Proof.

Let $R(X)$ be such a divisor of degree $r$ of $X^{n/s}+1$, then
$P(X)=R(X^{s})$ is a divisor of degree $sr$ of $X^{n}+1$ and it has no term in
$X$. ∎

In Corollary 2.3, the larger the $s$, the smaller the number of the values
reached by $k=sr$.

Remark. Here also we can take for $R(X)$ the product of the cyclotomic
polynomials of any distinct indices dividing $n/s$. The situation is simpler
than in Corollary 2.2, since there is no condition on $\epsilon$. But the
number of values reached by $k$ is smaller. Taking $n=12$ or $n=8$ does not
add new values of $k$ to those found in Corollary 2.2, but for $n=6$, we
obtain $k=2,4,6$ and 6 is new.

Case $\boldsymbol{n}$ odd. For $n$ odd, the divisors
$P(X)\in\mathbb{F}_{2}[X]$ of $X^{n}+1$ are the generator polynomials of the
binary cyclic codes of length $n$ over $\mathbb{F}_{2}$ [14]. Given any binary
cyclic code having for nonzeros 1 and at least another element, its generator
polynomial $g(X)$ satisfies $X^{n}+1=(X+1)g(X)h(X)$ for some binary (non-
trivial) polynomial $h(X)$, and one of the two polynomials $g(X)$ and $h(X)$
has no term in $X$, because $g(X)h(X)=(X^{n}+1)/(X+1)=\sum_{i=0}^{n-1}X^{i}$,
and the sum of the coefficients of $X$ in $g(X)$ and $h(X)$ equals then 1. If
$n$ is a prime, then the degree $k$ of this polynomial is co-prime with $n$.
We do not know in general whether $k$ equals the degree of $g$ or that of $h$;
if the code is the binary quadratic residue code, with $n\equiv\pm 1\pmod{8}$,
then these two polynomials having the same degree, we have $k=(n-1)/2$. But
there are values of $n$ for which the method does not work, because
$(X^{n}+1)/(X+1)$ is irreducible over $\mathbb{F}_{2}$; this happens if and
only if the cyclotomic class of 2 modulo $n$ containing 1 equals the whole
$(\mathbb{Z}/n\mathbb{Z})\setminus\\{0\\}$, that is, 2 is a primitive element
modulo $n$.

###  2.2. Why it is not enough to consider binary polynomials
$\boldsymbol{L_{E_{k}}}$, that is, binary matrices $\boldsymbol{A}$ only

For fixed $k$, there is a finite number (namely, $2^{k-2}$) of binary
companion $k\times k$ matrices $A$ of the form (2.1) such that $b_{0}=1$ and
$b_{1}=0$, and taking for $n$ a prime number strictly larger than all prime
numbers dividing the orders (necessarily larger than 1) of these matrices, we
see that, for every $k$, there are values of $n$ such that $A^{n}\neq I_{k}$
for every such matrix.

In [15], a particular type of trinomials of the form
$X^{q^{d}}+bX^{q}+aX\in\mathbb{F}_{q^{m}}[X]$ was studied, where $q$ is a
power of a prime111The conditions so that they split over $\mathbb{F}_{2^{n}}$
are strong and this means that almost all of such polynomials actually do not
split.. However,
\- if we take $q=2$ (and $m=n$), then since $b$ needs to be zero, being then
the coefficient of $X^{2}$, and the equation $x^{q^{d}}+ax=0$ splitting only
if $d$ divides $n$, we are back to the case where $k=d$ divides $n$;
\- if we assume that $m$ is a strict divisor of $n$ and $q=2^{n/m}$, then
$k=nd/m$ satisfies $\gcd(k,n)\geq n/m\geq 2$ and we get no new case where the
inverse function is not $k$th order sum-free either.

Note that when the number of cyclotomic classes (and hence, the maximal number
of the minimal polynomials which are factors of $L_{E_{k}}(X)$) is as small as
2 (this happens with some primes $n=3,5,11,13,19,29,37,53,59,61,\dots$), the
only factors with binary coefficients of $X^{2^{n}}+X$ are $X+1$ and
$\sum_{i=0}^{n-1}X^{2^{i}}$ and none has a coefficient of $X^{2}$ equal to 0.

With the observations above, we see that the question of determining whether
the multiplicative inverse function is $k$th order sum-free over
$\mathbb{F}_{2^{n}}$ for some $n$ and some $k$ not dividing $n$ is difficult,
unless $k$ is small or large.

##  3\. An Alternative Approach

In this section, we revisit, from the viewpoint of determinants, results from
[4, Theorem 2] and from Theorem 2.1 above. This new approach will also allow
us to prove in the next section that $F_{\text{\rm inv}}$ is not $k$th order
sum-free when $k$ is small or large (approximately $k\leq n/10$ or $k\geq
9n/10$).

###  3.1. An approach through determinants

Define

(3.1) $\Delta(X_{1},\dots,X_{k})=\left|\begin{matrix}X_{1}&\cdots&X_{k}\cr
X_{1}^{2}&\cdots&X_{k}^{2}\cr\vdots&&\vdots\cr
X_{1}^{2^{k-1}}&\cdots&X_{k}^{2^{k-1}}\end{matrix}\right|,$

and for $0\leq i\leq k$,

(3.2)
$\Delta_{i}(X_{1},\dots,X_{k})=\left|\begin{matrix}X_{1}&\cdots&X_{k}\cr\vdots&&\vdots\cr
X_{1}^{2^{i-1}}&\cdots&X_{k}^{2^{i-1}}\cr
X_{1}^{2^{i+1}}&\cdots&X_{k}^{2^{i+1}}\cr\vdots&&\vdots\cr
X_{1}^{2^{k}}&\cdots&X_{k}^{2^{k}}\end{matrix}\right|.$

These are polynomials in $\mathbb{Z}[X_{1},\dots,X_{k}]$. However, for our
purpose, we treat them as polynomials in $\mathbb{F}_{2}[X_{1},\dots,X_{k}]$;
$\Delta(X_{1},\dots,X_{k})$ is known as the Moore determinant over
$\mathbb{F}_{2}$ [17]. By [13, Lemma 3.51],

(3.3) $\Delta(X_{1},\dots,X_{k})=\prod_{{\bf
0}\neq(a_{1},\dots,a_{k})\in\mathbb{F}_{2}^{k}}(a_{1}X_{1}+\cdots+a_{k}X_{k})=\prod_{{\bf
0}\neq\boldsymbol{a}\in\mathbb{F}_{2}^{k}}(\boldsymbol{a}\cdot\boldsymbol{X}),$

where ${\bf 0}=(0,\dots,0)$, $\boldsymbol{X}=(X_{1},\dots,X_{k})$ and
$\boldsymbol{a}\cdot\boldsymbol{X}=a_{1}X_{1}+\cdots+a_{k}X_{k}$ for
$\boldsymbol{a}=(a_{1},\dots,a_{k})\in\mathbb{F}_{2}^{k}$. Obviously,
$\Delta_{0}(X_{1},\dots,X_{k})=\Delta(X_{1},\dots,X_{k})^{2}$ and
$\Delta_{k}(X_{1},\dots,$ $X_{k})=\Delta(X_{1},\dots,X_{k})$. However, for
$1\leq i\leq k-1$, the formula for $\Delta_{i}(X_{1},\dots,X_{k})$ is too
complicated to be useful; see [10, Appendix]. We also know that [9, Exercise
2.15]

$\displaystyle\prod_{\boldsymbol{a}\in\mathbb{F}_{2}^{k}}(Y+\boldsymbol{a}\cdot\boldsymbol{X})\,$
$\displaystyle=\frac{\Delta(Y,X_{1},\dots,X_{k})}{\Delta(X_{1},\dots,X_{k})}$
$\displaystyle=\frac{1}{\Delta(X_{1},\dots,X_{k})}\sum_{i=0}^{k}\Delta_{i}(X_{1},\dots,X_{k})Y^{2^{i}}$
$\displaystyle=\sum_{i=0}^{k}b_{ki}Y^{2^{i}},$

where

$b_{ki}=\frac{\Delta_{i}(X_{1},\dots,X_{k})}{\Delta(X_{1},\dots,X_{k})}.$

Let $v_{1},\dots,v_{k}\in\mathbb{F}_{2^{n}}$ be linearly independent over
$\mathbb{F}_{2}$. Then by [4],

(3.4) $\sum_{0\neq x\in\langle
v_{1},\dots,v_{k}\rangle}\frac{1}{x}=\frac{b_{k1}}{b_{k0}}=\frac{\Delta_{1}(v_{1},\dots,v_{k})}{\Delta(v_{1},\dots,v_{k})^{2}}.$

Therefore, $F_{\text{\rm inv}}$ is not $k$th order sum-free if and only if
there exist $v_{1},\dots,v_{k}\in\mathbb{F}_{2^{n}}$ such that
$\Delta_{1}(v_{1},\dots,v_{k})=0$ but $\Delta(v_{1},\dots,v_{k})\neq 0$.

The next theorem is equivalent to Theorem 2.1. We state and prove it for
clarity.

######  Theorem 3.1.

The following two statements are equivalent:

  * (i)

There exists $x\in\mathbb{F}_{2^{n}}$ such that
$\Delta(x,x^{2},x^{2^{2}},\dots,x^{2^{k-1}})\neq 0$ and
$\Delta_{1}(x,x^{2},x^{2^{2}},\dots,x^{2^{k-1}})=0$.

  * (ii)

$X^{n}-1$ has a factor
$X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}\in\mathbb{F}_{2}[X]$.

###### Proof.

Let $\sigma$ denote the Frobenius automorphism of $\mathbb{F}_{2^{n}}$ over
$\mathbb{F}_{2}$. Note that

$\displaystyle\Delta(x,x^{2},x^{2^{2}},\dots,x^{2^{k-1}})\neq 0$
$\displaystyle\Leftrightarrow\ $ $\displaystyle
x,\sigma(x),\dots,\sigma^{k-1}(x)\ \text{are linearly independent over}\
\mathbb{F}_{2},$

and

$\displaystyle\Delta_{1}(x,x^{2},x^{2^{2}},\dots,x^{2^{k-1}})=0$
$\displaystyle\Leftrightarrow\ $ $\displaystyle
x,\sigma^{2}(x),\dots,\sigma^{k}(x)\ \text{are linearly dependent over}\
\mathbb{F}_{2}.$

(ii) $\Rightarrow$ (i). Let $\alpha\in\mathbb{F}_{2^{n}}$ be a normal element
over $\mathbb{F}_{2}$. Write $X^{n}-1=fg$, where
$f=X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}$. Let $x=(g(\sigma))(\alpha)$.
For each $0\neq h\in\mathbb{F}_{2}[X]$ with $\deg h<k$, $hg\not\equiv
0\pmod{X^{n}-1}$, whence $(h(\sigma))(x)=((hg)(\sigma))(\alpha)\neq 0$. Hence
$x,\sigma(x),\dots,\sigma^{k-1}(x)$ are linearly independent over
$\mathbb{F}_{2}$.

Since $(f(\sigma))(x)=((fg)(\sigma))(\alpha)=0$, the elements
$x,\sigma^{2}(x),\dots,\sigma^{k}(x)$ are linearly dependent over
$\mathbb{F}_{2}$.

(i) $\Rightarrow$ (ii). Since $x,\sigma^{2}(x),\dots,\sigma^{k}(x)$ are
linearly dependent over $\mathbb{F}_{2}$, there exists $0\neq
f=a_{k}X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}\in\mathbb{F}_{2}[X]$ such
that $(f(\sigma))(x)=0$. We claim that $a_{k}\neq 0$ and $f\mid X^{n}-1$.
Otherwise, $f_{1}:=\text{gcd}(f,X^{n}-1)$ has degree $<k$ and
$(f_{1}(\sigma))(x)=0$. Then $x,\sigma(x),\dots,\sigma^{k-1}(x)$ are linearly
dependent over $\mathbb{F}_{2}$, which is a contradiction. ∎

######  Corollary 3.2.

If $X^{n}-1$ has a factor
$X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}\in\mathbb{F}_{2}[X]$, then
$F_{\text{\rm inv}}$ is not $k$th order sum-free.

Note. If we replace $k$ by $n-k$ in Corollary 3.2, we do not get anything new.

###  3.2. Factorization of $\boldsymbol{X^{n}-1}$ over
$\boldsymbol{\mathbb{F}_{2}}$

This is a well-studied topic, which we briefly revisit because of Corollary
3.2. We are interested in the factors of $X^{n}-1$ of the form
$X^{k}+a_{k-1}X^{k-1}+\cdots+a_{2}X^{2}+a_{0}$, where
$a_{i}\in\mathbb{F}_{2}$, or equivalently, by considering the reciprocals,
those of the form $X^{k}+a_{k-2}X^{k-2}+\cdots+a_{0}$.

Let $n=2^{e}t$, where $e\geq 0$ and $2\nmid t$, so that
$X^{n}-1=(X^{t}-1)^{2^{e}}$. Recall that $X^{t}-1=\prod_{d\mid t}\Phi_{d}(X)$,
where $\Phi_{d}$ is the cyclotomic polynomial of index $d$. For each $d\mid
t$, let $o_{d}(2)$ denote the order of $2$ in
$(\mathbb{Z}/d\mathbb{Z})^{\times}$. The irreducible factors of $\Phi_{d}(X)$
in $\mathbb{F}_{2}[X]$ correspond to the $2$-cyclotomic cosets in
$(\mathbb{Z}/d\mathbb{Z})^{\times}$ and their degrees equal the sizes of the
$2$-cyclotomic cosets. All $2$-cyclotomic cosets in
$(\mathbb{Z}/d\mathbb{Z})^{\times}$ have size $o_{d}(2)$ and there are
$\phi(d)/o_{d}(2)$ such cyclotomic cosets in
$(\mathbb{Z}/d\mathbb{Z})^{\times}$, where $\phi$ is Euler’s totient function.
Hence, the multiset of the degrees of the irreducible factors of $X^{t}-1$
over $\mathbb{F}_{2}$ consists of $o_{d}(2)$ with multiplicity
$\phi(d)/o_{d}(2)$ for all $d\mid t$.

For $d\mid t$, let $l=o_{d}(2)$, we have

$\displaystyle N_{d}\,$
$\displaystyle:=|\\{f=X^{l}+b_{l-2}X^{l-2}+\cdots+b_{0}\in\mathbb{F}_{2}[X]\
\text{irreducible}:f\mid X^{t}-1\\}|$
$\displaystyle=\frac{1}{l}|\\{x\in\mathbb{F}_{2^{l}}:o(x)=d,\
\text{Tr}(x)=0\\}|,$

where $o(x)$ denotes the multiplicative order of $x$ and
$\text{Tr}=\text{Tr}_{2^{l}/2}$. Indeed, if
$X^{l}+b_{l-1}X^{l-1}+b_{l-2}X^{l-2}+\cdots+b_{0}\in\mathbb{F}_{2}[X]$ is
irreducible and $x$ is a zero of this polynomial, then $b_{l-1}=\text{Tr}(x)$
and there are $l$ such zeros. Note that $N_{d}$ depends only on $l$ but not on
$t$. An irreducible polynomial in $\mathbb{F}_{2}[X]$ of the form
$X^{l}+b_{l-2}X^{l-2}+\cdots+b_{0}$ is said to have zero trace. Consider an
arbitrary factor $f$ of $X^{n}-1$. For each $d\mid t$, among the irreducible
factors of $f$ of degree $o_{d}(2)$, let $\mu_{d}$ be the number of those
(counting multiplicity) with zero trace and $\nu_{d}$ be the number of those
with nonzero trace. Then $\mu_{d}\leq 2^{e}N_{d}$ and $\mu_{d}+\nu_{d}\leq
2^{e}\phi(d)/o_{2}(d)$. Moreover, $f$ is of the form
$X^{k}+a_{k-2}X^{k-2}+\cdots+a_{0}$ if and only if $\sum_{d\mid t}\nu_{d}$ is
even. Therefore, $X^{n}-1$ has a factor
$X^{k}+a_{k-2}X^{k-2}+\cdots+a_{0}\in\mathbb{F}_{2}[X]$ if and only if

(3.5) $2\leq k=\sum_{d\mid t}(\mu_{d}+\nu_{d})o_{d}(2)$

for some integer sequences $\mu_{d}$ and $\nu_{d}$ such that

$\begin{cases}0\leq\mu_{d}\leq 2^{e}N_{d},\vspace{0.2em}\cr 0\leq\nu_{d}\leq
2^{e}(\phi(d)/o_{d}(2)-N_{d}),\vspace{0.3em}\cr\displaystyle\sum_{d\mid
t}\nu_{d}\equiv 0\pmod{2}.\end{cases}$

Let $\mathcal{K}_{n}$ denote the set of integers $k$ in (3.5). Then Corollary
3.2 can be stated as

######  Corollary 3.3.

$F_{\text{\rm inv}}$ is not $k$th order sum-free if $k\in\mathcal{K}_{n}$.

The values of $o_{d}(2)$, $\phi(d)/o_{d}(2)$ and $N_{d}$ ($1\leq d\leq 31$,
$d$ odd) are given in Table 1 and the sets $\mathcal{K}_{n}$ ($1\leq n\leq
32$) are given in Table 2. Note that the examples in Section 2 are covered by
Table 2.

Table 1. $o_{2}(d)$, $\phi(d)/o_{d}(2)$ and $N_{d}$ ($1\leq d\leq 31$, $d$ odd) $d$ | $o_{d}(2)$ | $\phi(d)/o_{d}(2)$ | $N_{d}$
---|---|---|---
1 | 1 | 1 | 0
3 | 2 | 1 | 0
5 | 4 | 1 | 0
7 | 3 | 2 | 1
9 | 6 | 1 | 1
11 | 10 | 1 | 0
13 | 12 | 1 | 0
15 | 4 | 2 | 1
17 | 8 | 2 | 1
19 | 18 | 1 | 0
21 | 6 | 2 | 1
23 | 11 | 2 | 1
25 | 20 | 1 | 1
27 | 18 | 1 | 1
29 | 28 | 1 | 0
31 | 5 | 6 | 3
Table 2. Elements of $\mathcal{K}_{n}$ ($1\leq n\leq 32$) $n$ | elements of $\mathcal{K}_{n}$
---|---
1 |
2 | 2
3 | 3
4 | 2,4
5 | 5
6 | 2,3,4,6
7 | 3,4,7
8 | 2,4,6,8
9 | 3,6,9
10 | 2,5,8,10
11 | 11
12 | 2,3,4,5,6,7,8,9,10,12
13 | 13
14 | 2,3,4,5,6,7,8,9,10,11,12,14
15 | 3,4,5,6,7,8,9,10,11,12,15
16 | 2,4,6,8,10,12,14,16
17 | 8,9,17
18 | 2,3,4,6,8,9,10,12,14,15,16,18
19 | 19
20 | 2,4,5,7,8,10,12,13,15,16,18,20
21 | 3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,21
22 | 2,11,20,22
23 | 11,12,23
24 | 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24
25 | 5,20,25
26 | 2,13,24,26
27 | 3,6,9,18,21,24,27
28 | 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,28
29 | 29
30 | 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,30
31 | 5,6,10,11,15,16,20,21,25,26,31
32 | 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32

######  Remark 3.4.

The number $N_{d}$ is difficult to compute. Let $l=o_{d}(2)$. We have

$\sum_{\begin{subarray}{c}x\in\mathbb{F}_{2^{l}}\cr
o(x)=d\end{subarray}}(-1)^{\text{Tr}(x)}=lN_{d}-(d-lN_{d})=2lN_{d}-d.$

On the other hand, by the Möbius inversion,

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathbb{F}_{2^{l}}\cr
o(x)=d\end{subarray}}(-1)^{\text{Tr}(x)}\,$
$\displaystyle=\sum_{d^{\prime}\mid
d}\mu\Bigl{(}\frac{d}{d^{\prime}}\Bigr{)}\sum_{\begin{subarray}{c}x\in\mathbb{F}_{2^{l}}\cr
o(x)\mid d^{\prime}\end{subarray}}(-1)^{\text{Tr}(x)}$
$\displaystyle=\sum_{d^{\prime}\mid
d}\mu\Bigl{(}\frac{d}{d^{\prime}}\Bigr{)}\frac{d^{\prime}}{2^{l}-1}\sum_{y\in\mathbb{F}_{2^{l}}^{*}}(-1)^{\text{Tr}(y^{(2^{l}-1)/d^{\prime}})}$
$\displaystyle=\sum_{d^{\prime}\mid
d}\mu\Bigl{(}\frac{d}{d^{\prime}}\Bigr{)}\frac{d^{\prime}}{2^{l}-1}\Bigl{(}\sum_{y\in\mathbb{F}_{2^{l}}}(-1)^{\text{Tr}(y^{(2^{l}-1)/d^{\prime}})}-1\Bigr{)},$

where $\mu(\ )$ is the Möbius function. Let $\widehat{\mathbb{F}_{2^{l}}^{*}}$
denote the group of multiplicative characters of $\mathbb{F}_{2^{l}}$. In the
above

$\sum_{y\in\mathbb{F}_{2^{l}}}(-1)^{\text{Tr}(y^{(2^{l}-1)/d^{\prime}})}=\sum_{\begin{subarray}{c}\chi\in\widehat{\mathbb{F}_{2^{l}}^{*}}\cr
o(\chi)\mid(2^{l}-1)/d^{\prime}\end{subarray}}G(\chi),$

where $G(\chi)$ is the Gauss sum of $\chi$ [9, Exercise 3.4]. Combining the
above equations gives

$N_{d}=\frac{1}{2l}\biggl{(}d+\sum_{d^{\prime}\mid
d}\mu\Bigl{(}\frac{d}{d^{\prime}}\Bigr{)}\frac{d^{\prime}}{2^{l}-1}\Bigl{(}\sum_{\begin{subarray}{c}\chi\in\widehat{\mathbb{F}_{2^{l}}^{*}}\cr
o(\chi)\mid(2^{l}-1)/d^{\prime}\end{subarray}}G(\chi)-1\Bigr{)}\biggr{)}.$

Because of the involvement of the Gauss sums, we doubt that $N_{d}$ can be
computed explicitly.

##  4\. When $k$ Is Small

The algebraic closure of a field $\mathbb{F}$ is denoted by
$\overline{\mathbb{F}}$. A polynomial $f\in\mathbb{F}[X_{1},\dots,X_{k}]$ is
said to be square-free if there is no
$g\in\mathbb{F}[X_{1},\dots,X_{k}]\setminus\mathbb{F}$ (equivalently, there is
no
$g\in\overline{\mathbb{F}}[X_{1},\dots,X_{k}]\setminus\overline{\mathbb{F}}$)
such that $g^{2}\mid f$. It is easy to see that $f$ is square-free if and only
for each $1\leq j\leq k$, $f$ is a separable polynomial in $X_{j}$. A
polynomial $f$ in $X$ over a field is separable if and only if
$\gcd(f,f^{\prime})=1$. It is clear from (3.3) that
$\Delta(X_{1},\dots,X_{k})$ is square-free. It follows from (3.2) that for
each $1\leq j\leq k$, $\Delta_{1}(X_{1},\dots,X_{k})$ is a $2$-polynomial in
$X_{j}$ whose coefficient of $X_{j}$ is nonzero, hence
$\Delta_{1}(X_{1},\dots,X_{k})$ is separable in $X_{j}$. Therefore,
$\Delta_{1}(X_{1},\dots,X_{k})$ is also square-free.

Recall from (3.3) that
$\Delta(\boldsymbol{X})=\prod_{\boldsymbol{0}\neq\boldsymbol{a}\in\mathbb{F}_{2}^{k}}\boldsymbol{a}\cdot\boldsymbol{X}$,
where $\boldsymbol{X}=(X_{1},\dots,X_{k})$. Let $0\leq i\leq k$. Clearly,
$\boldsymbol{a}\cdot\boldsymbol{X}\mid\Delta_{i}(\boldsymbol{X})$ for all
$\boldsymbol{0}\neq\boldsymbol{a}\in\mathbb{F}_{2}^{k}$. Hence
$\Delta(\boldsymbol{X})\mid\Delta_{i}(\boldsymbol{X})$. Let

(4.1)
$F_{k}(X_{1},\dots,X_{k})=\frac{\Delta_{1}(\boldsymbol{X})}{\Delta(\boldsymbol{X})}\in\mathbb{F}_{2}[X_{1},\dots,X_{k}].$

We first gather some facts about $F_{k}$:

  * •

$F_{k}$ is homogeneous and symmetric in $X_{1},\dots,X_{k}$.

  * •

$\deg F_{k}=2^{k}-2$, $\deg_{X_{i}}F_{k}=2^{k-1}$.

  * •

$F_{k}$ is square-free.

  * •

$F_{k}\in\mathbb{F}_{2}[X_{2},\dots,X_{k}][X_{1}]$ is an affine $2$-polynomial
in $X_{1}$, i.e., the exponents of $X_{1}$ in $F_{k}$ are
$0,2^{0},\dots,2^{k-1}$.

###### Proof of the last claim.

Treat both $\Delta_{1}(X_{1},\dots,X_{k})$ and $\Delta(X_{1},\dots,X_{k})$ as
polynomials in $X_{1}$. Then $\Delta_{1}(X_{1},\dots,X_{k})$ is a separable
$2$-polynomial with $\deg_{X_{1}}\Delta_{1}(X_{1},$ $\dots,X_{k})=2^{k}$.
Hence its roots (in the algebraic closure of
$\mathbb{F}_{2}(X_{2},\dots,X_{k})$) form a $k$-dimensional vector space $E$
over $\mathbb{F}_{2}$. The roots of $\Delta(X_{1},\dots,X_{k})$ form a
$(k-1)$-dimensional subspace of $E$. Therefore, the roots of
$F_{k}(X_{1},\dots,X_{k})$ form a $(k-1)$-dimensional affine space over
$\mathbb{F}_{2}$, hence the claim. ∎

For $0\leq i<j\leq k+1$, define

$\Delta_{ij}(X_{1},\dots,X_{k})=\left|\begin{matrix}X_{1}&\cdots&X_{k}\cr\vdots&&\vdots\cr
X_{1}^{2^{i-1}}&\cdots&X_{k}^{2^{i-1}}\cr
X_{1}^{2^{i+1}}&\cdots&X_{k}^{2^{i+1}}\cr\vdots&&\vdots\cr
X_{1}^{2^{j-1}}&\cdots&X_{k}^{2^{j-1}}\cr
X_{1}^{2^{j+1}}&\cdots&X_{k}^{2^{j+1}}\cr\vdots&&\vdots\cr
X_{1}^{2^{k+1}}&\cdots&X_{k}^{2^{k+1}}\end{matrix}\right|.$

From (4.1), we have

(4.2)
$\Delta_{1}(X_{1},\dots,X_{k})=\Delta(X_{1},\dots,X_{k})F_{k}(X_{1},\dots,X_{k}).$

Write

$\Delta_{1}(X_{1},\dots,X_{k})=A_{k}X_{1}^{2^{k}}+A_{k-1}X_{1}^{2^{k-1}}+\cdots+A_{2}X_{1}^{2^{2}}+A_{0}X_{1},$

where

$A_{i}=\begin{cases}\Delta(X_{2},\dots,X_{k})^{4}&\text{if}\
i=0,\cr\Delta_{1i}(X_{2},\dots,X_{k})&\text{if}\ 2\leq i\leq k,\end{cases}$

and write

$\Delta(X_{1},\dots,X_{k})=B_{k-1}X_{1}^{2^{k-1}}+B_{k-2}X_{1}^{2^{k-2}}+\cdots+B_{0}X_{1},$

where

$B_{i}=\Delta_{i}(X_{2},\dots,X_{k}),\quad 0\leq i\leq k-1.$

Further write

(4.3)
$F_{k}(X_{1},\dots,X_{k})=C_{k-1}X_{1}^{2^{k-1}}+C_{k-2}X_{1}^{2^{k-2}}+\cdots+C_{0}X_{1}+C_{-1},$

where $C_{i}\in\mathbb{F}_{2}[X_{2},\dots,X_{k}]$, $-1\leq i\leq k-1$. The
coefficients $C_{i}$ ($-1\leq i\leq k-1$) can be determined in terms of
$\Delta_{i}(X_{2},\dots,X_{k})$ by comparing the coefficients of $X_{1}$ in
(4.2). First, we have $C_{k-1}B_{k-1}=A_{k}$, whence

(4.4)
$C_{k-1}=\frac{A_{k}}{B_{k-1}}=\frac{\Delta_{1}(X_{2},\dots,X_{k})}{\Delta(X_{2},\dots,X_{k})}=F_{k-1}(X_{2},\dots,X_{k}).$

For $0\leq i\leq k-2$, we have $C_{k-1}B_{i}+C_{i}B_{k-1}=0$, whence

(4.5)
$C_{i}=C_{k-1}\frac{B_{i}}{B_{k-1}}=F_{k-1}(X_{2},\dots,X_{k})\frac{\Delta_{i}(X_{2},\dots,X_{k})}{\Delta(X_{2},\dots,X_{k})}.$

Finally, $C_{-1}B_{0}=A_{0}$, whence

(4.6)
$C_{-1}=\frac{A_{0}}{B_{0}}=\frac{\Delta(X_{2},\dots,X_{k})^{4}}{\Delta(X_{2},\dots,X_{k})^{2}}=\Delta(X_{2},\dots,X_{k})^{2}.$

As a by-product, we have a formula for $\Delta_{1i}(X_{2},\dots,X_{k})$ with
$2\leq i\leq k-1$. (There is no need to consider
$\Delta_{1k}(X_{2},\dots,X_{k})$ since
$\Delta_{1k}(X_{2},\dots,X_{k})=\Delta_{1}(X_{2},\dots,$ $X_{k})$.) From
(4.2), we have

$A_{i}=B_{i-1}C_{i-1}+B_{i}C_{-1}.$

Hence, with $\boldsymbol{X}^{\prime}=(X_{2},\dots,X_{k})$,

(4.7) $\displaystyle\Delta_{1i}(\boldsymbol{X}^{\prime})\,$
$\displaystyle=\Delta_{i-1}(\boldsymbol{X}^{\prime})\frac{\Delta_{1}(\boldsymbol{X}^{\prime})}{\Delta(\boldsymbol{X}^{\prime})}\frac{\Delta_{i-1}(\boldsymbol{X}^{\prime})}{\Delta(\boldsymbol{X}^{\prime})}+\Delta_{i}(\boldsymbol{X}^{\prime})\Delta(\boldsymbol{X}^{\prime})^{2}$
$\displaystyle=\frac{\Delta_{1}(\boldsymbol{X}^{\prime})(\Delta_{i-1}(\boldsymbol{X}^{\prime}))^{2}}{(\Delta(\boldsymbol{X}^{\prime}))^{2}}+\Delta_{i}(\boldsymbol{X}^{\prime})\Delta(\boldsymbol{X}^{\prime})^{2}.$

The polynomial $F_{k}(X_{1},\dots,X_{k})$ contains critical information about
the sum-freedom of $F_{\text{\rm inv}}$. Recall that $F_{\text{\rm inv}}$ is
not $k$th order sum-free if and only if there exist
$v_{1},\dots,v_{k}\in\mathbb{F}_{2^{n}}$ such that
$\Delta_{1}(v_{1},\dots,v_{k})=0$ but $\Delta(v_{1},\dots,v_{k})\neq 0$. By
(4.1), this happens if and only if there exist
$v_{1},\dots,v_{k}\in\mathbb{F}_{2^{n}}$ such that
$F_{k}(v_{1},\dots,v_{k})=0$ but $\Delta(v_{1},\dots,v_{k})\neq 0$.

A polynomial $f\in\mathbb{F}_{q}[X_{1},\dots,X_{k}]$ is said to be absolutely
irreducible if it is irreducible in
$\overline{\mathbb{F}}_{q}[X_{1},\dots,X_{k}]$. For
$f(X_{1},\dots,X_{k})\in\mathbb{F}_{q}[X_{1},\dots,X_{k}]$, define

$V_{\mathbb{F}_{q}^{k}}(f)=\\{(x_{1},\dots,x_{k})\in\mathbb{F}_{q}^{k}:f(x_{1},\dots,x_{k})=0\\}.$

######  Lemma 4.1.

When $k\geq 3$, $F_{k}(X_{1},\dots,X_{k})$ is absolutely irreducible.

###### Proof.

Since $k\geq 3$, $\deg F_{k-1}(X_{2},\dots,X_{k})>0$. Since
$\Delta_{1}(X_{2},\dots,X_{k})$ is square-free, we have by (4.4) that
$\text{gcd}(C_{k-1},\Delta(X_{2},\dots,X_{k}))=1$.
Hence by (4.6), $\text{gcd}(C_{k-1},C_{-1})=1$. Thus
$F_{k}(X_{1},\dots,X_{k})$ as a polynomial in $X_{1}$ over
$\overline{\mathbb{F}}_{2}[X_{2},\dots,X_{k}]$ is primitive (recall that a
polynomial over a unique factorization domain such as
$\bar{\mathbb{F}}_{2}[X_{2},...,X_{k}]$ is said to be primitive if the gcd of
its coefficients is 1). Let $f\in\overline{\mathbb{F}}_{2}[X_{2},\dots,X_{k}]$
be any irreducible factor of $C_{k-1}$. Then $f\mid C_{i}$ for $0\leq i\leq
k-1$ (by (4.5)), $f\nmid C_{-1}$, and $f^{2}\nmid C_{k-1}$. By Eisenstein’s
criterion [11, Chapter III, Theorem 6.15], $F_{k}(X_{1},\dots,X_{k})$ is
irreducible in $\overline{\mathbb{F}}_{2}[X_{1},\dots,X_{k}]$. ∎

Remark. When $k=2$, $F_{2}(X_{1},X_{2})$ is not absolutely irreducible. We
have

$F_{2}(X_{1},X_{2})=X_{1}^{2}+X_{1}X_{2}+X_{2}^{2}=(X_{1}+uX_{2})(X_{1}+(u+1)X_{2}),$

where $u\in\mathbb{F}_{2^{2}}\setminus\mathbb{F}_{2}$. Of course, every
homogeneous polynomial in two variables over a field $\mathbb{F}$ is a product
of linear polynomials over $\overline{\mathbb{F}}$.

######  Theorem 4.2.

Assume that $k\geq 3$ and

(4.8) $n\geq\frac{\log_{2}(1+\sqrt{21})}{3}(13k-6).$

Then $F_{\text{\rm inv}}$ is not $k$th order sum-free.

###### Proof.

Let $q=2^{n}$. It suffices to show that

$V_{\mathbb{F}_{q}^{k}}(F_{k})\not\subset
V_{\mathbb{F}_{q}^{k}}(\Delta(X_{1},\dots,X_{k})).$

Since $F_{k}$ is absolutely irreducible of degree $2^{k}-2$, by the Lang-Weil
bound, as stated in [2, Theorem 5.2],

$\displaystyle|V_{\mathbb{F}_{q}^{k}}(F_{k})|\,$ $\displaystyle\geq
q^{k-1}-(2^{k}-3)(2^{k}-4)q^{k-3/2}-5(2^{k}-2)^{13/3}q^{k-2}$
$\displaystyle>q^{k-1}-2^{2k}q^{k-3/2}-5\cdot 2^{13k/3}q^{k-2}.$

On the other hand, by [2, Lemma 2.2],

$|V_{\mathbb{F}_{q}^{k}}(F_{k})\cap
V_{\mathbb{F}_{q}^{k}}(\Delta(X_{1},\dots,X_{k}))|\leq(2^{k}-1)^{2}q^{k-2}<2^{2k}q^{k-2}.$

Hence it suffices to show that

(4.9) $q^{k-1}-2^{2k}q^{k-3/2}-5\cdot 2^{13k/3}q^{k-2}\geq 2^{2k}q^{k-2}.$

Let $y=q^{1/2}=2^{n/2}$. Then (4.9) is equivalent to

$y^{2}-2^{2k}y-(5\cdot 2^{13k/3}+2^{2k})\geq 0.$

Let $y_{0}$ denote the larger root of the quadratic $Y^{2}-2^{2k}Y-(5\cdot
2^{13k/3}+2^{2k})$. Then

$\displaystyle y_{0}\,$
$\displaystyle=\frac{1}{2}\bigl{(}2^{2k}+\sqrt{2^{4k}+20\cdot
2^{13k/3}+2^{2k+2}}\bigr{)}$
$\displaystyle\leq\frac{1}{2}\bigl{(}2^{2k}+\sqrt{21\cdot 2^{13k/3}}\bigr{)}$
$\displaystyle\leq\frac{1}{2}(1+\sqrt{21})2^{13k/6}.$

Therefore, it suffices to show that

$y=2^{n/2}\geq(1+\sqrt{21})2^{13k/6-1},$

i.e.,

$n\geq\frac{\log_{2}(1+\sqrt{21})}{3}(13k-6),$

which is given. Hence the proof is complete. ∎

Replacing $k$ with $n-k$ in Theorem 4.2 gives

######  Corollary 4.3.

Assume that $n-k\geq 3$ and

(4.10) $n\leq\frac{\log_{2}(1+\sqrt{21})}{13\log_{2}(1+\sqrt{21})-3}(13k+6).$

Then $F_{\text{\rm inv}}$ is not $(n-k)$th order sum-free.

######  Remark 4.4.

In Theorem 4.2, (4.8) is satisfied when

$n\geq 10.8k-5.$

In Corollary 4.3, (4.10) is satisfied when

$n\leq 1.1k+0.5.$

##  5\. The Case of Even $n$

The following lemma is a slight improvement of [4, Corollary 7]. More
precisely, the condition that $r\mid n$ in [4, Corollary 7] is removed.

######  Corollary 5.1.

Assume that $l\geq 2$, $l\mid n$, $r<n/l$, and that $F_{\text{\rm inv}}$ is
not $r$th order sum-free in $\mathbb{F}_{2^{n}}$. Then $F_{\text{\rm inv}}$ is
not $(l+r)$th order sum-free in $\mathbb{F}_{2^{n}}$.

###### Proof.

Let $E=\mathbb{F}_{2^{l}}\subset\mathbb{F}_{2^{n}}$. Then
$L_{E}(X)=X^{2^{l}}+X$. Let $F$ be an $r$-dimensional
$\mathbb{F}_{2}$-subspace of $\mathbb{F}_{2^{n}}$ such that $\sum_{0\neq v\in
F}1/v=0$. Let $F^{\prime}$ be the $\mathbb{F}_{2^{l}}$-span of $F$ in
$\mathbb{F}_{2^{n}}$. Then $\dim_{\mathbb{F}_{2^{l}}}F^{\prime}\leq
r<n/l=\dim_{\mathbb{F}_{2^{l}}}\mathbb{F}_{2^{n}}$. Hence there exists $0\neq
a\in\mathbb{F}_{2^{n}}$ such that $\text{Tr}_{2^{n}/2^{l}}(av)=0$ for all
$v\in F^{\prime}$, equivalently, $\text{Tr}_{2^{n}/2^{l}}(av)=0$ for all $v\in
F$. It follows that $aF\subset L_{E}(\mathbb{F}_{2^{n}})$. Since
$L_{E}:\mathbb{F}_{2^{n}}\to\mathbb{F}_{2^{n}}$ induces an isomorphism
$\mathbb{F}_{2^{n}}/E\to L_{E}(\mathbb{F}_{2^{n}})$, there exists an
$\mathbb{F}_{2}$-subspace $E^{\prime}$ of $\mathbb{F}_{2^{n}}$ of dimension
$r$ such that $E^{\prime}\cap E=\\{0\\}$ and $L_{E}(E^{\prime})=aF$. Now by
[4, Corollary 5],

$\sum_{0\neq u\in E\oplus E^{\prime}}\frac{1}{u}=\sum_{0\neq v\in
L_{E}(E^{\prime})}\frac{1}{v}=\sum_{0\neq v\in
F}\frac{1}{av}=\frac{1}{a}\sum_{0\neq v\in F}\frac{1}{v}=0.$

∎

Quite surprisingly, this slight improvement leads to a quick proof of
Conjecture 1.1 for all even $n$.

######  Theorem 5.2.

Assume that $n$ is even and $2\leq k\leq n-2$. Then $F_{\text{\rm inv}}$ is
not $k$th order sum-free.

###### Proof.

It suffices to consider odd $k$ with $3\leq k\leq n/2$. By [4, Corollary 10],
$F_{\text{\rm inv}}$ is not $3$rd order sum-free. If $3<n/2$, by Corollary
5.1, $F_{\text{\rm inv}}$ is not $(2+3)$th order sum-free. If $2+3<n/2$, by
Corollary 5.1 again, $F_{\text{\rm inv}}$ is not $(2+2+3)$th order sum-free.
In this way, all odd integers $k$ with $3\leq k\leq n/2$ are covered. ∎

## References

  * [1] F. E. Brochero Martinez, C. R. Giraldo Vergara and L. B. Oliveira, Explicit factorization of $x^{n}-1\in\mathbb{F}_{q}[x]$, Designs, Codes and Cryptography 77 (2015), 277 – 286.
  * [2] A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl. 12 (2006), 155 – 185.
  * [3] C. Carlet, Two generalizations of almost perfect nonlinearity, Cryptology ePrint Archive 2024/841.
  * [4] C. Carlet, On the vector subspaces of $\mathbb{F}_{2^{n}}$ over which the multiplicative inverse function sums to zero, Cryptology ePrint Archive 2024/1007.
  * [5] W. E. Clark, X. Hou and A. Mihailovs, The affinity of a permutation of a finite vector space, Finite Fields Appl. 13 (2007), 80 – 112.
  * [6] B. Csajbók, G. Marino, O. Polverino and F. Zullo, A characterization of linearized polynomials with maximum kernel, Finite Fields Appl. 56 (2019), 109 – 130.
  * [7] M.R. Darafsheh, Order of elements in the groups related to the general linear group, Finite Fields Appl. 11 (2005), 738 – 747.
  * [8] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
  * [9] X. Hou, Lectures on Finite Fields, Graduate Studies in Mathematics, vol. 190, American Mathematical Society, Providence, RI, 2018.
  * [10] X. Hou and C. Sze, On a radical extension of the field of rational functions in several variables, Linear and Multilinear Algebra, 71 (2023), 1015 – 1025.
  * [11] T. W. Hungerford, Algebra, Springer-Verlag, New York-Berlin, 1980.
  * [12] S. Lang, Cyclotomic Fields I and II, Graduate Texts in Mathematics 121, Springer-Verlag, New York, 1990.
  * [13] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.
  * [14] F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North Holland. 1977.
  * [15] G. McGuire and D. Mueller, Some results on linearized trinomials that split completely, Proceedings of Finite Fields and their Applications Fq14, pp.149 – 164, 2020.
  * [16] G. McGuire and J. Sheekey, A characterization of the number of roots of linearized and projective polynomials in the field of coefficients, Finite Fields Appl. 57 (2019), 68 – 91.
  * [17] E. H. Moore, A two-fold generalization of Fermat’s theorem, Bull. Amer. Math. Soc. 2 (1896), 189 – 199.
  * [18] K. Nyberg, Differentially uniform mappings for cryptography, Proceedings of EUROCRYPT’ 93, Lecture Notes in Computer Science 765, pp. 55-64, 1994.