\documentclass[11pt,a4paper,reqno]{amsart} \usepackage[a4paper,margin=1in]{geometry} \usepackage{amsmath,amssymb,amsfonts,mathtools} \usepackage{booktabs,array,tabularx} \usepackage{microtype} \usepackage{enumitem} \usepackage{xcolor} \usepackage{listings} \usepackage[hidelinks]{hyperref} \hypersetup{pdftitle={A Detailed Finite-Carry Proof of a Conjecture on Permutation Binomials in Characteristic Two},pdfauthor={Yi Li},pdfkeywords={permutation binomials,finite fields,Lucas theorem,finite carry proof}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{remark}[theorem]{Remark} \newtheorem{definition}[theorem]{Definition} \newcommand{\F}{\mathbb F} \newcommand{\Z}{\mathbb Z} \newcommand{\AND}{\mathbin{\&}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\calR}{\mathcal R} \newcommand{\Ind}{\mathbf{1}} \allowdisplaybreaks[2] \lstset{ basicstyle=\ttfamily\footnotesize, frame=single, breaklines=true, columns=fullflexible, showstringspaces=false, keepspaces=true, xleftmargin=0.2em, xrightmargin=0.2em, aboveskip=0.8em, belowskip=0.8em } \title[Proof of a conjecture on permutation binomials]{A Detailed Finite-Carry Proof of a Conjecture on\\ Permutation Binomials in Characteristic Two} \author{Yi Li} \thanks{Affiliation: School of Computer Science, Shanghai Jiao Tong University,\\ Shanghai 200240, China. E-mail: \texttt{yi.li@sjtu.edu.cn}.} \subjclass[2020]{11T06, 11T55, 05A05} \keywords{Permutation binomial, finite field, Lucas's theorem, binary carries, seventh roots of unity} \begin{document} \begin{abstract} Let $q=2^m$, where $m\ge5$ is odd and $3\mid m$. Tu, Zeng, Jiang and Li formulated a conjecture asserting that if a family of Hermite-type sums $S_{r,\alpha}(y)$, attached to the binomial $x^r(a+x^{3(q-1)})$, vanishes for every $\alpha$ with $3\mid(1+\alpha)$, then $y^3=1$. We give a detailed proof, including all exceptional and boundary cases. In fact, seven indices suffice: $\alpha\in\{2,8,14,20,26,32,38\}$. The first two indices reduce a hypothetical counterexample to a primitive seventh root of unity. Lucas's theorem then turns the remaining equations into six-bit conditions, and an explicit finite carry elimination completes the proof. The paper records the complete residue tables, their derivation, and a short SageMath verification certificate. \end{abstract} \maketitle \section{Introduction and statement of the result} Consider the binomial \begin{equation}\label{eq:binomial} f(X)=X^r\bigl(a+X^{3(q-1)}\bigr)\in\F_{q^2}[X], \qquad q=2^m. \end{equation} In their study of the permutation property of~\eqref{eq:binomial}, Tu, Zeng, Jiang and Li~\cite{TZJL} reduced the remaining necessity question, for $m$ odd and divisible by $3$, to the simultaneous vanishing of certain sums $S_{r,\alpha}(y)$, where $y=a^{(q+1)/3}$. They posed the following assertion as Conjecture~1 of~\cite{TZJL}. We state it for arbitrary nonzero $y$, which is the form useful below. \begin{theorem}[Conjecture 1 of Tu--Zeng--Jiang--Li]\label{thm:conjecture} Let \[ q=2^m,\qquad m\ge5\text{ odd},\qquad 3\mid m, \] and let $1\le r\le q$ and $y\in\F_{q^2}^{*}$. If \[ S_{r,\alpha}(y)=0 \quad\text{for every }0\le\alpha\le q-1 \text{ such that }3\mid(1+\alpha), \] then $y^3=1$. \end{theorem} The proof below establishes the following stronger version. \begin{theorem}[Seven-index strengthening]\label{thm:seven} Under the assumptions on $q,r,y$ in Theorem~\ref{thm:conjecture}, if \begin{equation}\label{eq:seven-indices} S_{r,\alpha}(y)=0 \quad\text{for }\alpha\in\{2,8,14,20,26,32,38\}, \end{equation} then $y^3=1$. \end{theorem} The point is that the conclusion is uniform in $m$ and $r$. Since $m\ge5$ is odd and divisible by $3$, necessarily $m\ge9$. Thus all seven indices in~\eqref{eq:seven-indices} belong to the range $0\le\alpha\le q-1$. We proceed as follows. Section~2 derives an exact two- or three-term formula from the original sums. Section~3 explains why $\alpha=2,8$ force any counterexample to be a primitive seventh root. Section~4 establishes the six-bit residue table. Sections~5 and~6 separately eliminate nonboundary and boundary values of a normalized real parameter. An appendix gives executable, exact-arithmetic certificates for the finite calculations. \section{Exact reduction of the sums by Lucas's theorem} \subsection{The original notation} Put \begin{equation}\label{eq:M} M=\frac{q+1}{3}. \end{equation} For $0\le\alpha\le q-1$ with $3\mid(1+\alpha)$, define the integer interval \begin{equation}\label{eq:I} I_{r,\alpha}= [\,-r(1+\alpha)+3\alpha-3(q-1),\,-r(1+\alpha)+3\alpha\,] \end{equation} and let $\ell_{r,\alpha}$ be the least integer $\ell$ for which $\ell(q+1)\in I_{r,\alpha}$. Following equation~(6) of~\cite{TZJL}, set \begin{equation}\label{eq:B-general} B_{r,\alpha} =q-1-\alpha+\frac{r(1+\alpha)}3+\ell_{r,\alpha}M. \end{equation} The reduced sum is \begin{equation}\label{eq:S-definition} S_{r,\alpha}(y) =\sum_{t\in T_{r,\alpha}}\sum_{i=0}^{\alpha} \binom{\alpha}{i} \binom{q-1-\alpha}{tM+B_{r,\alpha}-i} y^{\,t-3i}, \end{equation} where $T_{r,\alpha}=\{0,1\}$ or $\{0,1,2\}$ according as $I_{r,\alpha}$ contains two or three multiples of $q+1$. We interpret a binomial coefficient with an out-of-range lower argument as zero and work in characteristic two. For the chosen indices, write \begin{equation}\label{eq:alpha-c} \alpha_c=3c-1, \qquad C=\{1,3,5,7,9,11,13\}. \end{equation} Choose $x$ uniquely by \begin{equation}\label{eq:x} 0\le x0. \end{cases} \end{equation} Thus $S_{r,\alpha_c}$ has two terms exactly when $M\mid cx$. \end{lemma} \begin{proof} Write $r-3=hM+x$ with $h\in\Z$. Since $1+\alpha_c=3c$, the upper endpoint of $I_{r,\alpha_c}$ is \[ -3cr+3(3c-1)=-3c(r-3)-3. \] Also $q-1=3M-2$, so dividing the entire interval by $3$ gives \begin{equation}\label{eq:I-div-3} \frac13 I_{r,\alpha_c} =[\,-c(r-3)-3M+1,\,-c(r-3)-1\,]. \end{equation} An integer multiple of $q+1=3M$ in $I_{r,\alpha_c}$ corresponds precisely to an integer multiple of $M$ in~\eqref{eq:I-div-3}. Using $c(r-3)=(ch+s_c)M+w_c$, the latter interval is \[ [\,-(ch+s_c+3)M-w_c+1,\,-(ch+s_c)M-w_c-1\,]. \] If $w_c=0$, its only multiples of $M$ are $-(ch+s_c+2)M$ and $-(ch+s_c+1)M$. If $1\le w_c0. \end{cases} \] Substitution in~\eqref{eq:B-general}, with \[ B_{r,\alpha_c}=q-3c+cr+\ell_{r,\alpha_c}M =q+c(r-3)+\ell_{r,\alpha_c}M, \] gives $B_c=M-1$ for $w_c=0$ and $B_c=w_c-1$ otherwise. The lists of multiples give~\eqref{eq:T-exact} as well. \end{proof} \subsection{Why the binomial sum has exactly one Lucas term per layer} For nonnegative integers $u,v$, let $u\AND v$ denote their bitwise binary AND. For example, $14=(1110)_2$ and $11=(1011)_2$, so $14\AND11=(1010)_2=10$. \begin{lemma}[Unique Lucas contribution]\label{lem:Lucas} Let $0\le\alpha,\beta\le q-1$. Exactly one integer $i$ gives a nonzero product in $\F_2$ \[ \binom{\alpha}{i}\binom{q-1-\alpha}{\beta-i}, \] namely \begin{equation}\label{eq:and} i=\alpha\AND\beta. \end{equation} Consequently, \begin{equation}\label{eq:S-short} S_{r,\alpha_c}(y)= \sum_{t=0}^{\nu_c-1} y^{\,t-3\left(\alpha_c\AND(B_c+tM)\right)}, \qquad \nu_c=\begin{cases}2,&w_c=0,\\3,&w_c>0.\end{cases} \end{equation} \end{lemma} \begin{proof} Write $\alpha$ and $\beta$ in $m$ binary positions. Because $q-1=2^m-1$ has all $m$ positions equal to $1$, $\alpha$ and $q-1-\alpha$ have complementary binary supports. Lucas's theorem says that $\binom{\alpha}{i}$ is odd precisely when every $1$-bit of $i$ is in the support of $\alpha$. Similarly, $\binom{q-1-\alpha}{\beta-i}$ is odd precisely when every $1$-bit of $\beta-i$ is in the complementary support. There can be no binary carry between these disjoint supports; hence $\beta=i+(\beta-i)$ is the disjoint splitting of the $1$-bits of $\beta$ into the two complementary supports. It is unique, and the first part is exactly $i=\alpha\AND\beta$. For $w_c=0$, the relevant lower binomial arguments $\beta_t=B_c+tM$ are $M-1$ and $2M-1$. For $w_c>0$ they are $w_c-1$, $M+w_c-1$, $2M+w_c-1$. All lie in $[0,q-1]$, since $q-1=3M-2$. Thus the unique-term statement applies to each $t$ in~\eqref{eq:S-definition}, and yields~\eqref{eq:S-short}. \end{proof} \section{The first two indices: reduction to seventh roots} Because $m\ge9$, the identity $3M=2^m+1$ implies \begin{equation}\label{eq:M-residues} M\equiv3\pmod4,\qquad M\equiv11\pmod{16},\qquad M\equiv43\pmod{64}. \end{equation} Indeed, $3M\equiv1\pmod{2^k}$ for $k\le m$, and $3^{-1}$ modulo $4,16,64$ is $3,11,43$, respectively. \subsection{The four trinomials for \texorpdfstring{$\alpha=2$}{alpha=2}} For $c=1$ we have $\alpha_1=2$. If $x\ne0$, then $B_1=x-1$ and \[ S_{r,2}(y)=y^{-3i_0}+y^{1-3i_1}+y^{2-3i_2}, \quad i_t=2\AND(x-1+tM). \] Since $2=(10)_2$, only the bit of value $2$ is tested. Using $M\equiv3\pmod4$, we obtain the following complete table. \begin{table}[htbp] \centering\small \caption{The four possibilities for $S_{r,2}(y)$ when $x\ne0$.} \label{tab:P} \begin{tabular}{c c l} \toprule $x\bmod4$ & $(i_0,i_1,i_2)$ & $S_{r,2}(y)$ \\ \midrule $0$ & $(2,2,0)$ & $y^{-6}(1+y+y^8)$ \\ $1$ & $(0,2,2)$ & $y^{-5}(1+y+y^5)$ \\ $2$ & $(0,0,2)$ & $y^{-4}(1+y^4+y^5)$ \\ $3$ & $(2,0,0)$ & $y^{-6}(1+y^7+y^8)$ \\ \bottomrule \end{tabular} \end{table} Write \begin{equation}\label{eq:four-P} \begin{aligned} P_0(Y)&=1+Y+Y^8,&P_1(Y)&=1+Y+Y^5,\\ P_2(Y)&=1+Y^4+Y^5,&P_3(Y)&=1+Y^7+Y^8. \end{aligned} \end{equation} Since $y\ne0$, the vanishing of $S_{r,2}(y)$ in the trinomial case is equivalent to $P_i(y)=0$ for one of these four polynomials. \subsection{The six trinomials for \texorpdfstring{$\alpha=8$}{alpha=8}} For $c=3$ we have $\alpha_3=8$. In its trinomial case, put $b=B_3\bmod16$. Since $8=(1000)_2$, the value of $i_t=8\AND(B_3+tM)$ depends only on $b+11t\pmod{16}$. One obtains: \begin{table}[htbp] \centering\small \caption{All $16$ residues for the trinomial $S_{r,8}(y)$.} \label{tab:H-pattern} \begin{tabular}{c c c} \toprule $b\bmod16$ & $(i_0,i_1,i_2)$ & monomial-free polynomial \\ \midrule $0,1$ & $(0,8,0)$ & $H_6$ \\ $2,3,4$ & $(0,8,8)$ & $H_2$ \\ $5,6,7$ & $(0,0,8)$ & $H_3$ \\ $8,9$ & $(8,0,8)$ & $H_4$ \\ $10,11,12$ & $(8,0,0)$ & $H_5$ \\ $13,14,15$ & $(8,8,0)$ & $H_1$ \\ \bottomrule \end{tabular} \end{table} Here \begin{equation}\label{eq:six-H} \begin{aligned} H_1(Y)&=1+Y+Y^{26}, & H_2(Y)&=1+Y+Y^{23},\\ H_3(Y)&=1+Y^{22}+Y^{23}, & H_4(Y)&=1+Y^2+Y^{25},\\ H_5(Y)&=1+Y^{25}+Y^{26}, & H_6(Y)&=1+Y^{23}+Y^{25}. \end{aligned} \end{equation} For example, if $b\equiv13\pmod{16}$ then $(i_0,i_1,i_2)=(8,8,0)$ and \[ S_{r,8}(y)=y^{-24}+y^{-23}+y^2=y^{-24}H_1(y). \] \subsection{All \texorpdfstring{$24$}{24} common factors and the binomial exceptions} Put $Q(Y)=Y^2+Y+1$. Euclid's algorithm in $\F_2[Y]$ gives Table~\ref{tab:gcd}, recording every pair, not merely the two exceptional pairs. An executable verification is included in Appendix~\ref{app:certificate}. \begin{table}[htbp] \centering \caption{The $24$ gcds $\gcd(P_i,H_j)$ over $\F_2[Y]$; $Q=Y^2+Y+1$.} \label{tab:gcd} \begin{tabular}{c cccccc} \toprule & $H_1$ & $H_2$ & $H_3$ & $H_4$ & $H_5$ & $H_6$ \\ \midrule $P_0$ & $Q$ & $Q$ & $Q$ & $Q$ & $Q$ & $Q$ \\ $P_1$ & $P_1$ & $Q$ & $Q$ & $Q$ & $Q$ & $Q$ \\ $P_2$ & $Q$ & $Q$ & $Q$ & $Q$ & $P_2$ & $Q$ \\ $P_3$ & $Q$ & $Q$ & $Q$ & $Q$ & $Q$ & $Q$ \\ \bottomrule \end{tabular} \end{table} The two exceptional entries can also be seen without a gcd program. Modulo $P_1$, one has $Y^5=Y+1$, whence \[ Y^{25}=(Y^5)^5=(Y+1)^5 \equiv Y^5+Y^4+Y+1\equiv Y^4, \] and therefore $Y^{26}\equiv Y+1$. Hence $P_1\mid H_1$. Taking reciprocal polynomials shows that $P_2\mid H_5$. Moreover, \begin{equation}\label{eq:factorP} \begin{aligned} P_1(Y)&=(Y^2+Y+1)(Y^3+Y^2+1),\\ P_2(Y)&=(Y^2+Y+1)(Y^3+Y+1). \end{aligned} \end{equation} We also need to check the possibility of two-term sums. If $S_{r,2}$ is a binomial, then $x=0$, so $S_{r,8}$ is also binomial. Formula~\eqref{eq:S-short} gives \[ S_{r,2}(y)=y^{-6}+y,\qquad S_{r,8}(y)=y^{-24}+y. \] Their simultaneous vanishing implies $y^7=y^{25}=1$ and hence $y=1$. If $S_{r,2}$ is a trinomial but $S_{r,8}$ is a binomial, the second equation gives $y^{25}=1$. However, $\ord(y)$ divides $q^2-1=4^m-1$, and because $m$ is odd, \[ 4^m-1\equiv(-1)^m-1\equiv3\pmod5. \] Thus $\gcd(25,q^2-1)=1$, so $y=1$. This is impossible for a three-term sum in characteristic two, since $S_{r,2}(1)=1+1+1=1$. We have proved the following key lemma. \begin{lemma}[Reduction to seventh roots]\label{lem:seventh} If $S_{r,2}(y)=S_{r,8}(y)=0$ and $y^3\ne1$, then precisely one of \begin{equation}\label{eq:two-cubics} y^3+y+1=0,\qquad y^3+y^2+1=0 \end{equation} holds. In either case $y\in\F_8^*$ has multiplicative order $7$. \end{lemma} \begin{proof} The binomial possibilities have just been excluded. If both sums are trinomials, $y$ is a common root of some $P_i,H_j$. Table~\ref{tab:gcd} shows that either $Q(y)=0$ or $P_1(y)=0$ or $P_2(y)=0$. The first possibility gives $y^3=1$, contrary to the hypothesis. Factoring the latter two polynomials as in~\eqref{eq:factorP} gives~\eqref{eq:two-cubics}. Each cubic in~\eqref{eq:two-cubics} has no root in $\F_2$ and hence is irreducible. Its nonzero roots lie in $\F_8^*$, a cyclic group of prime order $7$. The roots are not $1$, so their order is $7$. They cannot satisfy both cubics, since subtracting the equations would give $y^2+y=0$, which is incompatible with either cubic. \end{proof} \section{Fano-plane relations and the six-bit table} Suppose from now on, for contradiction, that all seven sums in~\eqref{eq:seven-indices} vanish but $y^3\ne1$. By Lemma~\ref{lem:seventh}, $y$ is a primitive seventh root. We use the terminology \begin{equation}\label{eq:type} \begin{array}{ll} \text{type }+:&y^3+y+1=0,\\ \text{type }-:&y^3+y^2+1=0. \end{array} \end{equation} \subsection{Reduction to six binary positions} Set \begin{equation}\label{eq:theta-rho} \theta=\frac{x}{M}\in[0,1),\qquad \rho=x\pmod{64}, \end{equation} where $\rho$ is always represented by an integer in $\{0,\ldots,63\}$. For each $c\in C$ put $k_c=\lfloor c\theta\rfloor$. If $c\theta\notin\Z$, then $w_c=cx-k_cM$ lies in $\{1,\ldots,M-1\}$, so~\eqref{eq:B-exact} and~\eqref{eq:M-residues} yield \begin{equation}\label{eq:b-formula} b_c:=B_c\pmod{64} \equiv c\rho-43k_c-1\pmod{64}. \end{equation} If $c\theta\in\Z$, the sum is instead a binomial, with \begin{equation}\label{eq:B-bin-mod} B_c\equiv M-1\equiv42\pmod{64}. \end{equation} Since $\alpha_c=3c-1\le38<64$, the binary AND with $\alpha_c$ uses only the lowest six bits of $B_c+tM$. Thus, in the trinomial case, the exponents may be reduced modulo $7$ as \begin{equation}\label{eq:e} e_t\equiv t-3\left(\alpha_c\AND\bigl((b_c+43t)\bmod64\bigr)\right) \pmod7,\quad t=0,1,2. \end{equation} The vanishing condition is exactly \begin{equation}\label{eq:3sum} y^{e_0}+y^{e_1}+y^{e_2}=0. \end{equation} \subsection{Why the exponent sets are translates of two triples} \begin{lemma}[The seven additive lines]\label{lem:fano} Let $y\in\F_8^*$ have order $7$. For three integers $e_0,e_1,e_2$, the equality~\eqref{eq:3sum} holds if and only if the residues $e_0,e_1,e_2$ are distinct and, for some $h\in\Z/7\Z$, \begin{equation}\label{eq:fano} \{e_0,e_1,e_2\}\equiv \begin{cases} h+\{0,1,3\}\pmod7,&\text{type }+,\\ h+\{0,2,3\}\pmod7,&\text{type }-. \end{cases} \end{equation} \end{lemma} \begin{proof} For type $+$, the defining equation is $1+y+y^3=0$. Multiplying by $y^h$ gives $y^h+y^{h+1}+y^{h+3}=0$, which proves sufficiency of the seven translates of $\{0,1,3\}$. Similarly, type $-$ gives the seven translates of $\{0,2,3\}$. For necessity, if two of the three exponents agree modulo $7$, their two equal powers cancel in characteristic two and the remaining nonzero power cannot vanish. Hence all three powers are distinct. In $\F_8$, each unordered pair of distinct nonzero elements $a,b$ uniquely determines the zero-sum triple $\{a,b,a+b\}$. There are $\binom72=21$ pairs, and every triple contains three pairs, so there are exactly $21/3=7$ zero-sum triples. The seven translates above are distinct (a nonzero translation of $\Z/7\Z$ cannot stabilize a three-element subset), so they exhaust all possibilities. \end{proof} For reference, the type $+$ lines are \begin{equation}\label{eq:plus-lines} \begin{gathered} \{0,1,3\},\{1,2,4\},\{2,3,5\},\{3,4,6\},\\ \{0,4,5\},\{1,5,6\},\{0,2,6\}, \end{gathered} \end{equation} whereas the type $-$ lines are \begin{equation}\label{eq:minus-lines} \begin{gathered} \{0,2,3\},\{1,3,4\},\{2,4,5\},\{3,5,6\},\\ \{0,4,6\},\{0,1,5\},\{1,2,6\}. \end{gathered} \end{equation} These are the seven lines of the additive Fano plane of $\F_8$. \subsection{Derivation and complete statement of the residue table} For each $c\in C$, let $\calR_c^+$ (respectively $\calR_c^-$) denote the set of residues $b_c\bmod64$ for which the trinomial vanishes at a type $+$ (respectively type $-$) seventh root. Equations~\eqref{eq:e} and~\eqref{eq:fano} make this a finite test of $64$ residues for each $c$. For a set $A\subseteq\Z/64\Z$, the notation $A+d\Z_{64}$ means all residues congruent modulo $d$ to some member of $A$. \begin{table}[htbp] \centering\small \caption{Complete permissible trinomial residues $b_c\pmod{64}$.} \label{tab:residues} \renewcommand{\arraystretch}{1.2} \begin{tabular}{c >{\raggedright\arraybackslash}p{0.38\textwidth} >{\raggedright\arraybackslash}p{0.38\textwidth}} \toprule $c$ & $\calR_c^+$ & $\calR_c^-$ \\ \midrule $1$ & $1+4\Z_{64}$ & $4\Z_{64}$ \\ $3$ & $\{10,11,12\}+16\Z_{64}$ & $\{13,14,15\}+16\Z_{64}$ \\ $5$ & $\{10,12,14\}+16\Z_{64}$ & $\{11,13,15\}+16\Z_{64}$ \\ $7$ & $\{9,16,18,19\}+32\Z_{64}$ & $\{0,22,23,25\}+32\Z_{64}$ \\ $9$ & $\{1,7,9,11,13,16,19\}+32\Z_{64}$ & $\{0,2,8,22,25,28,30\}+32\Z_{64}$ \\ $11$ & $\{32,33,\ldots,41\}$ & $\{0,1,\ldots,9\}$ \\ $13$ & $\{0,8,13,15,38,49,58,60\}$ & $\{3,26,28,33,41,45,47,56\}$ \\ \bottomrule \end{tabular} \end{table} Here are three hand-checkable examples. \begin{enumerate}[label=\textup{(\roman*)},leftmargin=2.3em] \item \emph{$c=1$.} Here $\alpha_1=2$ and $43\equiv3\pmod4$. For $b_1\equiv0,1,2,3\pmod4$, respectively, the triples $(e_0,e_1,e_2)\pmod7$ are \[ (0,2,3),\qquad(0,1,3),\qquad(1,1,2),\qquad(1,2,2). \] Thus $\calR_1^+=1+4\Z_{64}$ and $\calR_1^-=4\Z_{64}$. \item \emph{$c=3$.} Here $\alpha_3=8$ and only $b_3\pmod{16}$ matters. The six groups of $b_3$ in Table~\ref{tab:H-pattern} give the exponent triples \[ (0,5,2),\ (0,5,6),\ (0,1,6),\ (4,1,6),\ (4,1,2),\ (4,5,2). \] Only the fifth group is a type $+$ line: $\{4,1,2\}=1+\{0,1,3\}$. Only the sixth group is a type $-$ line: $\{4,5,2\}=2+\{0,2,3\}$. This gives the second row of Table~\ref{tab:residues}. \item \emph{$c=13$, one entry.} Here $\alpha_{13}=38$. If $b_{13}=0$, the three six-bit inputs $b_{13}+43t\pmod{64}$ are $0,43,22$. Their ANDs with $38$ are $0,34,6$, so \[ (e_0,e_1,e_2)=(0,1-3\cdot34,2-3\cdot6) \equiv(0,4,5)\pmod7. \] Since $\{0,4,5\}=4+\{0,1,3\}$, the residue $b_{13}=0$ belongs to $\calR_{13}^+$. The other entries are obtained by the same six-bit calculation, as verified in Appendix~\ref{app:certificate}. \end{enumerate} Notice that the seven residues $b_c$ in Table~\ref{tab:residues} are \emph{not independent}: by~\eqref{eq:b-formula}, all depend on the same pair $(\theta,\rho)$. This dependence drives the elimination. \section{Elimination of the nonboundary carry states} We first assume that \begin{equation}\label{eq:open-assumption} c\theta\notin\Z \quad\text{for every }c\in C. \end{equation} Equivalently, $\theta$ is not any breakpoint $j/c$ with $0\le j\le c$ and $c\in C$. Hence all seven sums under consideration are trinomials, so Table~\ref{tab:residues} applies without exception. \subsection{Deriving the four surviving regions} Since $0\le\theta<1$, we have $k_1=0$, and therefore \begin{equation}\label{eq:b-first-three} b_1\equiv\rho-1,\qquad b_3\equiv3\rho-43k_3-1,\qquad b_5\equiv5\rho-43k_5-1\pmod{64}. \end{equation} The $c=1$ row of Table~\ref{tab:residues} gives \begin{equation}\label{eq:rho-mod4} \rho\equiv \begin{cases} 2\pmod4,&\text{type }+,\\ 1\pmod4,&\text{type }-. \end{cases} \end{equation} Now $k_3=\lfloor3\theta\rfloor\in\{0,1,2\}$. For $c=3$ only reduction modulo $16$ is needed, and $43\equiv11\pmod{16}$ gives \[ b_3\equiv3\rho-11k_3-1\pmod{16}. \] Checking $\rho=2,6,10,14\pmod{16}$ for type $+$ and $\rho=1,5,9,13\pmod{16}$ for type $-$ yields: \begin{table}[htbp] \centering \caption{Survivors after imposing $c=1,3$; an empty entry means no residue survives.} \label{tab:c3-survivors} \begin{tabular}{c c c c} \toprule $k_3$ & interval for $\theta$ & type $+$: $\rho\pmod{16}$ & type $-$: $\rho\pmod{16}$ \\ \midrule $0$ & $(0,\tfrac13)$ & none & $5$ \\ $1$ & $(\tfrac13,\tfrac23)$ & $2$ & $9$ \\ $2$ & $(\tfrac23,1)$ & $6$ & none \\ \bottomrule \end{tabular} \end{table} To illustrate: for type $+$ and $k_3=1$, the four possible values $\rho\equiv2,6,10,14\pmod{16}$ give $3\rho-12\equiv10,6,2,14\pmod{16}$. Only $10$ lies in $\{10,11,12\}$, so $\rho\equiv2\pmod{16}$. Next $k_5=\lfloor5\theta\rfloor$, where $k_5=j$ corresponds to the open interval $(j/5,(j+1)/5)$. The $c=5$ condition is \begin{equation}\label{eq:b5-mod16} b_5\equiv5\rho-11k_5-1\pmod{16},\qquad \begin{cases} b_5\in\{10,12,14\},&\text{type }+,\\ b_5\in\{11,13,15\},&\text{type }-. \end{cases} \end{equation} For each of the four nonempty entries in Table~\ref{tab:c3-survivors}, testing the compatible $k_5$'s leaves just the rows below. The displayed $b_5$ values are reduced modulo $16$. \begin{table}[htbp] \centering\small \caption{All survivors after $c=1,3,5$: the carry indices and resulting intervals.} \label{tab:four} \begin{tabular}{c cc c c c} \toprule Type & $k_3$ & $k_5$ & interval for $\theta$ & $\rho\pmod{16}$ & $b_5\pmod{16}$ \\ \midrule $+$ & 1 & 1 & $(\tfrac13,\tfrac25)$ & 2 & 14 \\ $+$ & 2 & 3 & $(\tfrac23,\tfrac45)$ & 6 & 12 \\ $-$ & 0 & 1 & $(\tfrac15,\tfrac13)$ & 5 & 13 \\ $-$ & 1 & 3 & $(\tfrac35,\tfrac23)$ & 9 & 11 \\ \bottomrule \end{tabular} \end{table} For example, in the first row, $\rho\equiv2\pmod{16}$ gives $b_5\equiv9-11k_5\pmod{16}$. Of the compatible values $k_5=1,2,3$, only $k_5=1$ gives a permitted type $+$ residue ($14$), and \[ (\tfrac13,\tfrac23)\cap(\tfrac15,\tfrac25) =(\tfrac13,\tfrac25). \] The other three rows follow by exactly the same calculation. Because we ultimately work modulo $64$, each class modulo $16$ corresponds to four residues. Thus Table~\ref{tab:four} is precisely the following table. \begin{table}[htbp] \centering \caption{The four nonboundary states after $c=1,3,5$.} \label{tab:table2} \begin{tabular}{c c l} \toprule Type & interval for $\theta$ & possible $\rho\pmod{64}$ \\ \midrule $+$ & $(\tfrac13,\tfrac25)$ & $\{2,18,34,50\}$ \\ $+$ & $(\tfrac23,\tfrac45)$ & $\{6,22,38,54\}$ \\ $-$ & $(\tfrac15,\tfrac13)$ & $\{5,21,37,53\}$ \\ $-$ & $(\tfrac35,\tfrac23)$ & $\{9,25,41,57\}$ \\ \bottomrule \end{tabular} \end{table} We now eliminate these four regions. Each numerical residue below is obtained from~\eqref{eq:b-formula}, and the permissible residues are given in Table~\ref{tab:residues}. \subsection{Eliminating the type-plus regions} \paragraph{First region: \texorpdfstring{$1/3<\theta<2/5$}{1/310/13$. In either case, \[ b_{13}\equiv13\cdot6-43k_{13}-1 \equiv\begin{cases}10,&k_{13}=9,\\31,&k_{13}=10\end{cases} \pmod{64}. \] Neither $10$ nor $31$ belongs to $\calR_{13}^+=\{0,8,13,15,38,49,58,60\}$. Thus this interval is empty as well. \end{enumerate} We conclude that \emph{both} type $+$ regions are impossible. \subsection{Eliminating the type-minus regions} \paragraph{First region: \texorpdfstring{$1/5<\theta<1/3$}{1/53/13$; consequently \[ b_{13}\equiv10\ \text{or}\ 31\pmod{64}. \] Neither value lies in $\calR_{13}^-=\{3,26,28,33,41,45,47,56\}$. Hence the first type $-$ region is impossible. \paragraph{Second region: \texorpdfstring{$3/5<\theta<2/3$}{3/50$ we have $c=1$ in the trinomial case, and thus Table~\ref{tab:residues} imposes \begin{equation}\label{eq:boundary-first-filter} \rho\equiv \begin{cases} 2\pmod4,&\text{type }+,\\ 1\pmod4,&\text{type }-. \end{cases} \end{equation} Using~\eqref{eq:boundary-rho}, this produces the short list in Table~\ref{tab:boundary}. For instance, when $d=11$, equation~\eqref{eq:boundary-rho} becomes $\rho\equiv33j\pmod{64}$, hence $\rho\equiv j\pmod4$. For type $+$ this allows $j=2,6,10$; for type $-$ it allows $j=1,5,9$. The cases $d=3$ and $d=9$ are just as elementary. The point $\theta=0$ needs a special comment: then $x=0$, and $S_{r,2}(y)=y^{-6}+y=0$ for any primitive seventh root $y$. Thus it survives the first filter for both types, despite being binomial rather than trinomial. \begin{table}[htbp] \centering\small \caption{All boundary states surviving $c=1$, and their $c=3$ data. For a trinomial entry, $b_3$ is shown modulo $64$.} \label{tab:boundary} \begin{tabular}{c c r l} \toprule Type & $\theta$ & $\rho$ & $c=3$ value \\ \midrule $+$ & $0$ & 0 & binomial: $B_3\equiv42$ \\ $+$ & $2/11$ & 2 & $b_3\equiv5$ \\ $+$ & $2/9$ & 38 & $b_3\equiv49$ \\ $+$ & $6/11$ & 6 & $b_3\equiv38$ \\ $+$ & $2/3$ & 50 & binomial: $B_3\equiv42$ \\ $+$ & $10/11$ & 10 & $b_3\equiv7$ \\ \midrule $-$ & $0$ & 0 & binomial: $B_3\equiv42$ \\ $-$ & $1/11$ & 33 & $b_3\equiv34$ \\ $-$ & $1/3$ & 57 & binomial: $B_3\equiv42$ \\ $-$ & $5/11$ & 37 & $b_3\equiv3$ \\ $-$ & $7/9$ & 5 & $b_3\equiv56$ \\ $-$ & $9/11$ & 41 & $b_3\equiv36$ \\ \bottomrule \end{tabular} \end{table} \subsection{Excluding the remaining boundary states with \texorpdfstring{$c=3$}{c=3}} For every trinomial entry in Table~\ref{tab:boundary}, one has $k_3=\lfloor3\theta\rfloor$ and $b_3\equiv3\rho-43k_3-1\pmod{64}$. The four type $+$ entries give \[ b_3\equiv5,49,38,7\pmod{64}, \quad b_3\bmod16\in\{5,1,6,7\}, \] whereas $\calR_3^+$ requires $b_3\bmod16\in\{10,11,12\}$. Likewise, the four type $-$ entries give \[ b_3\equiv34,3,56,36\pmod{64}, \quad b_3\bmod16\in\{2,3,8,4\}, \] whereas $\calR_3^-$ requires $\{13,14,15\}\pmod{16}$. Thus all eight trinomial entries are excluded. The only remaining distinct boundary values are $\theta=0,1/3,2/3$, for which $3\theta\in\Z$. The corresponding $c=3$ sums are binomials with \[ B_3\equiv42\pmod{64},\qquad B_3+M\equiv21\pmod{64}. \] Since $\alpha_3=8$, the two Lucas indices are \[ i_0=8\AND42=8,\qquad i_1=8\AND21=0. \] Thus the exponents are $-24$ and $1$. For a primitive seventh root, these are $4$ and $1$ modulo $7$, which are distinct, and two nonzero powers of a characteristic-two field cannot add to zero unless they agree. Equivalently, $y^{-24}+y=0$ would imply $y^{25}=1$, incompatible with $\ord(y)=7$. \begin{proposition}[No boundary seventh-root solutions]\label{prop:boundary} No breakpoint $\theta=x/M$ can satisfy all seven vanishing conditions~\eqref{eq:seven-indices} at a primitive seventh root of either type. \end{proposition} \section{Proof of the theorems} \begin{proof}[Proof of Theorem~\ref{thm:seven}] Assume~\eqref{eq:seven-indices}. Suppose, for contradiction, that $y^3\ne1$. Lemma~\ref{lem:seventh} then forces $y$ to have order $7$ and to be of type $+$ or type $-$. The number $\theta=x/M$ is either a breakpoint or is not. Proposition~\ref{prop:open} rules out the nonboundary case; Proposition~\ref{prop:boundary} rules out the boundary case. Both possibilities give a contradiction. Therefore $y^3=1$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:conjecture}] The hypotheses of Theorem~\ref{thm:conjecture} include the seven indices in~\eqref{eq:seven-indices}. Apply Theorem~\ref{thm:seven}. \end{proof} \begin{remark} For $m\ge9$, the only congruence about $M$ needed for the final elimination is $M\equiv43\pmod{64}$. The reduction is thus uniform in the original field size, and the remaining checks are exact calculations on six binary digits. The proof uses finite enumerations as explicit certificates, not a numerical search over arbitrarily large finite fields. \end{remark} \appendix \section{Reproducible finite certificates in SageMath}\label{app:certificate} For completeness, the short SageMath code below verifies Tables~\ref{tab:gcd} and~\ref{tab:residues}, then checks every open carry cell and every arithmetically possible boundary. It uses integer modular arithmetic and exact rational arithmetic; no floating-point comparisons are involved. The code is supplementary to the case-by-case elimination in Sections~5--6. \subsection*{A.1. The \texorpdfstring{$24$}{24} polynomial gcds} \begin{lstlisting} R. = PolynomialRing(GF(2)) P = [1+Y+Y^8, 1+Y+Y^5, 1+Y^4+Y^5, 1+Y^7+Y^8] H = [1+Y+Y^26, 1+Y+Y^23, 1+Y^22+Y^23, 1+Y^2+Y^25, 1+Y^25+Y^26, 1+Y^23+Y^25] Q = Y^2+Y+1 for i in range(4): for j in range(6): expected = P[1] if (i, j) == (1, 0) else ( P[2] if (i, j) == (2, 4) else Q) assert gcd(P[i], H[j]) == expected assert P[1] == Q * (Y^3+Y^2+1) assert P[2] == Q * (Y^3+Y+1) \end{lstlisting} \subsection*{A.2. The six-bit residue table and all carry states} The predicate \texttt{zero} uses Lemma~\ref{lem:fano} for three terms and equality of the two exponent classes for two terms. The last loops cover all the breakpoints $j/c$, all the open intervals between consecutive breakpoints, and both root types. \begin{lstlisting} from fractions import Fraction C = (1, 3, 5, 7, 9, 11, 13) BASE = {'+': (0, 1, 3), '-': (0, 2, 3)} LINES = {t: {frozenset((h+a) % 7 for a in base) for h in range(7)} for t, base in BASE.items()} def zero(c, b, typ, n=3): A = 3*c-1 e = [(t-3*(A & ((b+43*t) % 64))) % 7 for t in range(n)] if n == 2: return e[0] == e[1] return len(set(e)) == 3 and frozenset(e) in LINES[typ] # Reconstruct Table 1 (all seven rows and both types). for c in C: for typ in ('+', '-'): allowed = [b for b in range(64) if zero(c,b,typ)] print(c,typ,allowed) # Each open cell has fixed floor(c*theta), for all c in C. D = sorted({Fraction(j,c) for c in C for j in range(c+1)}) assert len(D) == 42 def is_survivor(theta, rho, typ): for c in C: v = c*theta if v.denominator == 1: b,n = 42,2 else: k = v.numerator // v.denominator b,n = (c*rho-43*k-1) % 64,3 if not zero(c,b,typ,n): return False return True for typ in ('+', '-'): for a,b in zip(D,D[1:]): mid = (a+b)/2 assert not any(is_survivor(mid,rho,typ) for rho in range(64)) for theta in D[:-1]: d,j = theta.denominator,theta.numerator if d not in (1,3,9,11): continue # not realizable as x/M rho = (43*j*pow(d,-1,64)) % 64 assert not is_survivor(theta,rho,typ) print('All six-bit checks passed.') \end{lstlisting} \begin{thebibliography}{9} \bibitem{TZJL} Z.~Tu, X.~Zeng, Y.~Jiang and Y.~Li, \emph{Binomial permutations over finite fields with even characteristic}, Designs, Codes and Cryptography \textbf{89} (2021), 2869--2888, \url{https://doi.org/10.1007/s10623-021-00959-4}. \end{thebibliography} \end{document}