betaFeedback

WorksMathematics

A DETAILED FINITE-CARRY PROOF OF A CONJECTURE ON PERMUTATION BINOMIALS IN CHARACTERISTIC TWO

Abstract

Let q = 2m, where m ≥ 5 is odd and 3 | m. Tu, Zeng, Jiang and Li formulated a conjecture asserting that if a family of Hermite-type sums Sr,α(y), attached to the binomial xr(a+ x3(q−1)), vanishes for every α with 3 | (1 + α), then y3 = 1. We give a detailed proof, including all exceptional and boundary cases. In fact, seven indices suffice: α ∈ {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.

Introduction and statement of the result

Consider the binomial

f(X)=Xr(a+X3(q−1))∈Fq2[X],q=2m.(1)f(X) = X^r\left(a + X^{3(q-1)}\right) \in\mathbb{F}_{q^2}[X], \qquad q = 2^m. \tag*{(1)}

In their study of the permutation property of (1), Tu, Zeng, Jiang and Li [1] reduced the remaining necessity question, for mm odd and divisible by 33, to the simultaneous vanishing of certain sums Sr,α(y)S_{r,\alpha}(y), where y=a(q+1)/3y = a^{(q+1)/3}. They posed the following assertion as Conjecture 1 of [1]. We state it for arbitrary nonzero yy, which is the form useful below.

Theorem 1.1 (Conjecture 1 of Tu–Zeng–Jiang–Li). Let

q=2m,m≥5 odd,3∣m,q = 2^m, \qquad m \ge5\ \text{odd}, \qquad3 \mid m,

and let 1≤r≤q1 \le r \le q and y∈Fq2∗y \in\mathbb{F}_{q^2}^{*}. If

Sr,α(y)=0for every 0≤α≤q−1 such that 3∣(1+α),S_{r,\alpha}(y) = 0 \quad\text{for every } 0 \le\alpha\le q - 1 \text{ such that } 3 \mid(1+\alpha),

then y3=1y^3 = 1.

The proof below establishes the following stronger version.

Theorem 1.2 (Seven-index strengthening). Under the assumptions on qq, rr, yy in Theorem 1.1, if

Sr,α(y)=0for α∈{2,8,14,20,26,32,38},(2)S_{r,\alpha}(y) = 0 \quad\text{for } \alpha\in\{2, 8, 14, 20, 26, 32, 38\}, \tag*{(2)}

then y3=1y^3 = 1.

The point is that the conclusion is uniform in mm and rr. Since m≥5m \ge5 is odd and divisible by 33, necessarily m≥9m \ge9. Thus all seven indices in (2) belong to the range 0≤α≤q−10 \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 α=2,8\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.

2020 Mathematics Subject Classification. 11T06, 11T55, 05A05.

Key words and phrases. Permutation binomial, finite field, Lucas’s theorem, binary carries, seventh roots of unity.

Exact reduction of the sums by Lucas’s theorem

The original notation

Put

M=q+13.(3)M=\frac{q+1}{3}. \tag*{(3)}

For 0≤α≤q−10\le\alpha\le q-1 with 3∣(1+α)3\mid(1+\alpha), define the integer interval

Ir,α=[−r(1+α)+3α−3(q−1),−r(1+α)+3α](4)I_{r,\alpha}=[-r(1+\alpha)+3\alpha-3(q-1),-r(1+\alpha)+3\alpha] \tag*{(4)}

and let ℓr,α\ell_{r,\alpha} be the least integer ℓ\ell for which ℓ(q+1)∈Ir,α\ell(q+1)\in I_{r,\alpha}. Following equation (6) of [1], set

Br,α=q−1−α+r(1+α)3+ℓr,αM.(5)B_{r,\alpha}=q-1-\alpha+\frac{r(1+\alpha)}{3}+\ell_{r,\alpha}M. \tag*{(5)}

The reduced sum is

Sr,α(y)=∑t∈Tr,α∑i=0α(αi)(q−1−αtM+Br,α−i)yt−3i,(6)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}, \tag*{(6)}

where Tr,α={0,1}T_{r,\alpha}=\{0,1\} or {0,1,2}\{0,1,2\} according as Ir,αI_{r,\alpha} contains two or three multiples of q+1q+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

αc=3c−1,C={1,3,5,7,9,11,13}.(7)\alpha_c=3c-1,\qquad C=\{1,3,5,7,9,11,13\}. \tag*{(7)}

Choose xx uniquely by

0≤x<M,x≡r−3(modM),(8)0\le x<M,\qquad x\equiv r-3\pmod M, \tag*{(8)}

and for each cc write

cx=scM+wc,sc∈Z,0≤wc<M.(9)cx=s_cM+w_c,\qquad s_c\in\mathbb{Z},\qquad0\le w_c<M. \tag*{(9)}

The following exact computation is the basis of the proof.

Lemma 2.1 (Exact value of Br,αcB_{r,\alpha_c}). For every cc such that 0≤αc≤q−10\le\alpha_c\le q-1, one has

Br,αc=Bc={M−1,wc=0,wc−1,1≤wc<M,(10)B_{r,\alpha_c}=B_c= \begin{cases} M-1,&w_c=0,\\ w_c-1,&1\le w_c<M, \end{cases} \tag*{(10)}

and

Tr,αc={{0,1},wc=0,{0,1,2},wc>0.(11)T_{r,\alpha_c}= \begin{cases} \{0,1\},&w_c=0,\\ \{0,1,2\},&w_c>0. \end{cases} \tag*{(11)}

Thus Sr,αcS_{r,\alpha_c} has two terms exactly when M∣cxM\mid cx.

Proof. Write r−3=hM+xr-3=hM+x with h∈Zh\in\mathbb{Z}. Since 1+αc=3c1+\alpha_c=3c, the upper endpoint of Ir,αcI_{r,\alpha_c} is

−3cr+3(3c−1)=−3c(r−3)−3.-3cr+3(3c-1)=-3c(r-3)-3.

Also q−1=3M−2q-1=3M-2, so dividing the entire interval by 33 gives

13Ir,αc=[−c(r−3)−3M+1,−c(r−3)−1].(12)\frac{1}{3}I_{r,\alpha_c}=[-c(r-3)-3M+1,-c(r-3)-1]. \tag*{(12)}

An integer multiple of q+1=3Mq+1=3M in Ir,αcI_{r,\alpha_c} corresponds precisely to an integer multiple of MM in (2.10). Using c(r−3)=(ch+sc)M+wcc(r-3)=(ch+s_c)M+w_c, the latter interval is

[−(ch+sc+3)M−wc+1,−(ch+sc)M−wc−1].[-(ch+s_c+3)M-w_c+1,-(ch+s_c)M-w_c-1].

If wc=0w_c=0, its only multiples of MM are −(ch+sc+2)M-(ch+s_c+2)M and −(ch+sc+1)M-(ch+s_c+1)M. If 1≤wc<M1\le w_c<M, its only multiples of MM are −(ch+sc+3)M-(ch+s_c+3)M, −(ch+sc+2)M-(ch+s_c+2)M and −(ch+sc+1)M-(ch+s_c+1)M. (The endpoint inequalities are inclusive; this is why the case wc=0w_c=0 must be treated separately.) It follows that

ℓr,αc={−ch−sc−2,wc=0,−ch−sc−3,wc>0.\ell_{r,\alpha_c}= \begin{cases} -ch-s_c-2,&w_c=0,\\ -ch-s_c-3,&w_c>0. \end{cases}

Substitution in (2.3), with

Br,αc=q−3c+cr+ℓr,αcM=q+c(r−3)+ℓr,αcM,B_{r,\alpha_c}=q-3c+cr+\ell_{r,\alpha_c}M=q+c(r-3)+\ell_{r,\alpha_c}M,

gives Bc=M−1B_c=M-1 for wc=0w_c=0 and Bc=wc−1B_c=w_c-1 otherwise. The lists of multiples give (11) as well. □

Why the binomial sum has exactly one Lucas term per layer

For nonnegative integers u,vu,v, let u&vu\mathbin{\&}v denote their bitwise binary AND. For example, 14=(1110)214=(1110)_2 and 11=(1011)211=(1011)_2, so 14&11=(1010)2=1014\mathbin{\&}11=(1010)_2=10.

Lemma 2.2 (Unique Lucas contribution). Let 0≤α,β≤q−10\le\alpha,\beta\le q-1. Exactly one integer ii gives a nonzero product in F2\mathbb{F}_2

(αi)(q−1−αβ−i),\binom{\alpha}{i}\binom{q-1-\alpha}{\beta-i},

namely

i=α&β.(13)i=\alpha\mathbin{\&}\beta. \tag*{(13)}

Consequently,

Sr,αc(y)=∑t=0νc−1yt−3(αc&(Bc+tM)),νc={2,wc=0,3,wc>0.(14)S_{r,\alpha_c}(y)=\sum_{t=0}^{\nu_c-1}y^{t-3(\alpha_c\mathbin{\&}(B_c+tM))},\qquad \nu_c= \begin{cases} 2,&w_c=0,\\ 3,&w_c>0. \end{cases} \tag*{(14)}

Proof. Write α\alpha and β\beta in mm binary positions. Because q−1=2m−1q-1=2^m-1 has all mm positions equal to 11, α\alpha and q−1−αq-1-\alpha have complementary binary supports. Lucas’s theorem says that (αi)\binom{\alpha}{i} is odd precisely when every 1-bit of ii is in the support of α\alpha. Similarly, (q−1−αβ−i)\binom{q-1-\alpha}{\beta-i} is odd precisely when every 1-bit of β−i\beta-i is in the complementary support. There can be no binary carry between these disjoint supports; hence β=i+(β−i)\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=α&βi=\alpha\mathbin{\&}\beta.

For wc=0w_c=0, the relevant lower binomial arguments βt=Bc+tM\beta_t=B_c+tM are M−1M-1 and 2M−12M-1. For wc>0w_c>0 they are wc−1w_c-1, M+wc−1M+w_c-1, 2M+wc−12M+w_c-1. All lie in [0,q−1][0,q-1], since q−1=3M−2q-1=3M-2. Thus the unique-term statement applies to each tt in (6), and yields (2.12). □

The first two indices: reduction to seventh roots

Because m≥9m\ge9, the identity 3M=2m+13M=2^m+1 implies

M≡3(mod4),M≡11(mod16),M≡43(mod64).(15)M\equiv3\pmod{4},\qquad M\equiv11\pmod{16},\qquad M\equiv43\pmod{64}. \tag*{(15)}

Indeed, 3M≡1(mod2k)3M\equiv1\pmod{2^k} for k≤mk\le m, and 3−13^{-1} modulo 44, 1616, 6464 is 33, 1111, 4343, respectively.

The four trinomials for α=2\alpha=2

For c=1c=1 we have α1=2\alpha_1=2. If x≠0x\ne0, then B1=x−1B_1=x-1 and

Sr,2(y)=y−3i0+y1−3i1+y2−3i2,it=2&(x−1+tM).S_{r,2}(y)=y^{-3i_0}+y^{1-3i_1}+y^{2-3i_2},\qquad i_t=2\mathbin{\&}(x-1+tM).

Since 2=(10)22=(10)_2, only the bit of value 22 is tested. Using M≡3(mod4)M\equiv3\pmod{4}, we obtain the following complete table.

xx mod 4(i0,i1,i2)(i_0,i_1,i_2)Sr,2(y)S_{r,2}(y)
0(2,2,0)(2,2,0)y−6(1+y+y8)y^{-6}(1+y+y^8)
1(0,2,2)(0,2,2)y−5(1+y+y5)y^{-5}(1+y+y^5)
2(0,0,2)(0,0,2)y−4(1+y4+y5)y^{-4}(1+y^4+y^5)
3(2,0,0)(2,0,0)y−6(1+y7+y8)y^{-6}(1+y^7+y^8)

Table 1. The four possibilities for Sr,2(y)S_{r,2}(y) when x≠0x\ne0.

Write

P0(Y)=1+Y+Y8,P1(Y)=1+Y+Y5,P_0(Y)=1+Y+Y^8,\qquad P_1(Y)=1+Y+Y^5,
P2(Y)=1+Y4+Y5,P3(Y)=1+Y7+Y8.(16)P_2(Y)=1+Y^4+Y^5,\qquad P_3(Y)=1+Y^7+Y^8. \tag*{(16)}

Since y≠0y\ne0, the vanishing of Sr,2(y)S_{r,2}(y) in the trinomial case is equivalent to Pi(y)=0P_i(y)=0 for one of these four polynomials.

The six trinomials for alpha=8

For c=3c=3 we have α3=8\alpha_3=8. In its trinomial case, put b=B3 mod 16b=B_3\bmod16. Since 8=(1000)28=(1000)_2, the value of it=8&(B3+tM)i_t=8\mathbin{\&}(B_3+tM) depends only on b+11tb+11t (mod 16). One obtains:

Here

H1(Y)=1+Y+Y26,H2(Y)=1+Y+Y23,H3(Y)=1+Y22+Y23,H4(Y)=1+Y2+Y25,H5(Y)=1+Y25+Y26,H6(Y)=1+Y23+Y25.(17)\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}. \tag*{(17)} \end{aligned}

For example, if b≡13(mod16)b\equiv13\pmod{16} then (i0,i1,i2)=(8,8,0)(i_0,i_1,i_2)=(8,8,0) and

Sr,8(y)=y−24+y−23+y2=y−24H1(y).S_{r,8}(y)=y^{-24}+y^{-23}+y^2=y^{-24}H_1(y).

All 24 common factors and the binomial exceptions

Put Q(Y)=Y2+Y+1Q(Y)=Y^2+Y+1. Euclid’s algorithm in F2[Y]\mathbb{F}_2[Y] gives Table 3, recording every pair, not merely the two exceptional pairs. An executable verification is included in Appendix § 8.

The two exceptional entries can also be seen without a gcd program. Modulo P1P_1, one has Y5=Y+1Y^5=Y+1, whence

Y25=(Y5)5=(Y+1)5≡Y5+Y4+Y+1≡Y4,Y^{25}=(Y^5)^5=(Y+1)^5\equiv Y^5+Y^4+Y+1\equiv Y^4,

and therefore Y26≡Y+1Y^{26}\equiv Y+1. Hence P1∣H1P_1\mid H_1. Taking reciprocal polynomials shows that P2∣H5P_2\mid H_5. Moreover,

P1(Y)=(Y2+Y+1)(Y3+Y2+1),P2(Y)=(Y2+Y+1)(Y3+Y+1).(18)\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). \tag*{(18)} \end{aligned}

We also need to check the possibility of two-term sums. If Sr,2S_{r,2} is a binomial, then x=0x=0, so Sr,8S_{r,8} is also binomial. Formula (14) gives

Sr,2(y)=y−6+y,Sr,8(y)=y−24+y.S_{r,2}(y)=y^{-6}+y,\qquad S_{r,8}(y)=y^{-24}+y.

Their simultaneous vanishing implies y7=y25=1y^7=y^{25}=1 and hence y=1y=1. If Sr,2S_{r,2} is a trinomial but Sr,8S_{r,8} is a binomial, the second equation gives y25=1y^{25}=1. However, ord⁡(y)\operatorname{ord}(y) divides q2−1=4m−1q^2-1=4^m-1, and because mm is odd,

4m−1=(−1)m−1≡3(mod5).4^m-1=(-1)^m-1\equiv3\pmod5.

Thus gcd⁡(25,q2−1)=1\gcd(25,q^2-1)=1, so y=1y=1. This is impossible for a three-term sum in characteristic two, since Sr,2(1)=1+1+1=1S_{r,2}(1)=1+1+1=1.

We have proved the following key lemma.

Lemma 3.1 (Reduction to seventh roots). If Sr,2(y)=Sr,8(y)=0S_{r,2}(y)=S_{r,8}(y)=0 and y3≠1y^3 \ne1, then precisely one of

y3+y+1=0,y3+y2+1=0(19)y^3+y+1=0,\qquad y^3+y^2+1=0 \tag*{(19)}

holds. In either case y∈F8∗y\in\mathbb{F}_8^* has multiplicative order 7.

Proof. The binomial possibilities have just been excluded. If both sums are trinomials, yy is a common root of some Pi,HjP_i,H_j. Table 3 shows that either Q(y)=0Q(y)=0 or P1(y)=0P_1(y)=0 or P2(y)=0P_2(y)=0. The first possibility gives y3=1y^3=1, contrary to the hypothesis. Factoring the latter two polynomials as in (18) gives (19). Each cubic in (19) has no root in F2\mathbb{F}_2 and hence is irreducible. Its nonzero roots lie in F8∗\mathbb{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 y2+y=0y^2+y=0, which is incompatible with either cubic. □

H1H_1H2H_2H3H_3H4H_4H5H_5H6H_6
P0P_0QQQQQQQQQQQQ
P1P_1P1P_1QQQQQQQQQQ
P2P_2QQQQQQQQP2P_2QQ
P3P_3QQQQQQQQQQQQ

Table 3. The 24 gcds gcd⁡(Pi,Hj)\gcd(P_i,H_j) over F2[Y]\mathbb{F}_2[Y]; Q=Y2+Y+1Q=Y^2+Y+1.

Fano-plane relations and the six-bit table

Suppose from now on, for contradiction, that all seven sums in (2) vanish but y3≠1y^3\ne1. By Lemma 3.1, yy is a primitive seventh root. We use the terminology

type +:y3+y+1=0,type −:y3+y2+1=0.(20)\begin{aligned} \text{type }+ &: \quad y^3+y+1=0,\\ \text{type }- &: \quad y^3+y^2+1=0. \tag*{(20)} \end{aligned}

Reduction to six binary positions

Set

θ=xM∈[0,1),ρ=x(mod64),(21)\theta=\frac{x}{M}\in[0,1),\qquad\rho=x\pmod{64}, \tag*{(21)}

where ρ\rho is always represented by an integer in {0,…,63}\{0,\ldots,63\}. For each c∈Cc\in\mathcal{C} put kc=⌊cθ⌋k_c=\lfloor c\theta\rfloor. If cθ∉Zc\theta\notin\mathbb{Z}, then wc=cx−kcMw_c=cx-k_cM lies in {1,…,M−1}\{1,\ldots,M-1\}, so (2.8) and (3.1) yield

bc:=Bc(mod64)≡cρ−43kc−1(mod64).(22)b_c:=B_c\pmod{64}\equiv c\rho-43k_c-1\pmod{64}. \tag*{(22)}

If cθ∈Zc\theta\in\mathbb{Z}, the sum is instead a binomial, with

Bc≡M−1≡42(mod64).(23)B_c\equiv M-1\equiv42\pmod{64}. \tag*{(23)}

Since αc=3c−1≤38<64\alpha_c=3c-1\le38<64, the binary AND with αc\alpha_c uses only the lowest six bits of Bc+tMB_c+tM. Thus, in the trinomial case, the exponents may be reduced modulo 7 as

et≡t−3(αc&((bc+43t)(mod64)))(mod7),t=0,1,2.(24)e_t\equiv t-3\left(\alpha_c\mathbin{\&}\left((b_c+43t)\pmod{64}\right)\right)\pmod{7},\qquad t=0,1,2. \tag*{(24)}

The vanishing condition is exactly

ye0+ye1+ye2=0.(25)y^{e_0}+y^{e_1}+y^{e_2}=0. \tag*{(25)}

Why the exponent sets are translates of two triples

Lemma 4.1 (The seven additive lines). Let y∈F8∗y\in\mathbb{F}_8^* have order 7. For three integers e0,e1,e2e_0,e_1,e_2, the equality (25) holds if and only if the residues e0,e1,e2e_0,e_1,e_2 are distinct and, for some h∈Z/7Zh\in\mathbb{Z}/7\mathbb{Z},

{e0,e1,e2}≡{h+{0,1,3}(mod7),type +,h+{0,2,3}(mod7),type −.(26)\{e_0,e_1,e_2\}\equiv \begin{cases} h+\{0,1,3\} & \pmod{7},\quad\text{type }+,\\ h+\{0,2,3\} & \pmod{7},\quad\text{type }-. \end{cases} \tag*{(26)}

Proof. For type ++, the defining equation is 1+y+y3=01+y+y^3=0. Multiplying by yhy^h gives yh+yh+1+yh+3=0y^h+y^{h+1}+y^{h+3}=0, which proves sufficiency of the seven translates of {0,1,3}\{0,1,3\}. Similarly, type −- gives the seven translates of {0,2,3}\{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 F8\mathbb{F}_8, each unordered pair of distinct nonzero elements a,ba,b uniquely determines the zero-sum triple {a,b,a+b}\{a,b,a+b\}. There are (72)=21\binom{7}{2}=21 pairs, and every triple contains three pairs, so there are exactly 21/3=721/3=7 zero-sum triples. The seven translates above are distinct (a nonzero translation of Z/7Z\mathbb{Z}/7\mathbb{Z} cannot stabilize a three-element subset), so they exhaust all possibilities. □

:::

For reference, the type + lines are

{0,1,3}, {1,2,4}, {2,3,5}, {3,4,6},{0,4,5}, {1,5,6}, {0,2,6},(27)\{0,1,3\},\ \{1,2,4\},\ \{2,3,5\},\ \{3,4,6\},\\ \{0,4,5\},\ \{1,5,6\},\ \{0,2,6\}, \tag*{(27)}

whereas the type −- lines are

{0,2,3}, {1,3,4}, {2,4,5}, {3,5,6},{0,4,6}, {0,1,5}, {1,2,6}.(28)\{0,2,3\},\ \{1,3,4\},\ \{2,4,5\},\ \{3,5,6\},\\ \{0,4,6\},\ \{0,1,5\},\ \{1,2,6\}. \tag*{(28)}

These are the seven lines of the additive Fano plane of F8\mathbb{F}_8.

Derivation and complete statement of the residue table

For each c∈Cc \in C, let Rc+R_c^{+} (respectively Rc−R_c^{-}) denote the set of residues bcb_c mod 64 for which the trinomial vanishes at a type ++ (respectively type −-) seventh root. Equations (24) and (26) make this a finite test of 64 residues for each cc. For a set A⊆Z/64ZA \subseteq\mathbb{Z}/64\mathbb{Z}, the notation A+dZ64A+d\mathbb{Z}_{64} means all residues congruent modulo dd to some member of AA.

Here are three hand-checkable examples.

(i) c=1c=1. Here α1=2\alpha_1=2 and 43≡3(mod4)4^3\equiv3\pmod{4}. For b1≡0,1,2,3(mod4)b_1\equiv0,1,2,3\pmod{4}, respectively, the triples (e0,e1,e2)(mod7)(e_0,e_1,e_2)\pmod{7} are

(0,2,3),(0,1,3),(1,1,2),(1,2,2).(0,2,3),\qquad(0,1,3),\qquad(1,1,2),\qquad(1,2,2).

Thus R1+=1+4Z64R_1^{+}=1+4\mathbb{Z}_{64} and R1−=4Z64R_1^{-}=4\mathbb{Z}_{64}.

(ii) c=3c=3. Here α3=8\alpha_3=8 and only b3(mod16)b_3\pmod{16} matters. The six groups of b3b_3 in Table 2 give the exponent triples

bb mod 16(i0,i1,i2)(i_0,i_1,i_2)monomial-free polynomial
0, 1(0,8,0)(0,8,0)H6H_6
2, 3, 4(0,8,8)(0,8,8)H2H_2
5, 6, 7(0,0,8)(0,0,8)H3H_3
8, 9(8,0,8)(8,0,8)H4H_4
10, 11, 12(8,0,0)(8,0,0)H5H_5
13, 14, 15(8,8,0)(8,8,0)H1H_1

Table 2. All 16 residues for the trinomial Sr,8(y)S_{r,8}(y).

(0,5,2),(0,5,6),(0,1,6),(4,1,6),(4,1,2),(4,5,2).(0,5,2),\qquad(0,5,6),\qquad(0,1,6),\qquad(4,1,6),\qquad(4,1,2),\qquad(4,5,2).

Only the fifth group is a type + line: {4,1,2}=1+{0,1,3}\{4,1,2\}=1+\{0,1,3\}. Only the sixth group is a type −- line: {4,5,2}=2+{0,2,3}\{4,5,2\}=2+\{0,2,3\}. This gives the second row of Table 4.

ccRc+R_c^{+}Rc−R_c^{-}
11+4Z641+4\mathbb{Z}_{64}4Z644\mathbb{Z}_{64}
3{10,11,12}+16Z64\{10,11,12\}+16\mathbb{Z}_{64}{13,14,15}+16Z64\{13,14,15\}+16\mathbb{Z}_{64}
5{10,12,14}+16Z64\{10,12,14\}+16\mathbb{Z}_{64}{11,13,15}+16Z64\{11,13,15\}+16\mathbb{Z}_{64}
7{9,16,18,19}+32Z64\{9,16,18,19\}+32\mathbb{Z}_{64}{0,22,23,25}+32Z64\{0,22,23,25\}+32\mathbb{Z}_{64}
9{1,7,9,11,13,16,19}+32Z64\{1,7,9,11,13,16,19\}+32\mathbb{Z}_{64}{0,2,8,22,25,28,30}+32Z64\{0,2,8,22,25,28,30\}+32\mathbb{Z}_{64}
11{32,33,…,41}\{32,33,\ldots,41\}{0,1,…,9}\{0,1,\ldots,9\}
13{0,8,13,15,38,49,58,60}\{0,8,13,15,38,49,58,60\}{3,26,28,33,41,45,47,56}\{3,26,28,33,41,45,47,56\}

Table 4. Complete permissible trinomial residues bcb_c (mod 64).

(iii) c=13c=13, one entry. Here α13=38\alpha_{13}=38. If b13=0b_{13}=0, the three six-bit inputs b13+43t(mod64)b_{13}+4^3t\pmod{64} are 0,43,220,43,22. Their ANDs with 38 are 0,34,60,34,6, so

(e0,e1,e2)=(0,1−3⋅34,2−3⋅6)≡(0,4,5)(mod7).(e_0,e_1,e_2)=(0,1-3\cdot34,2-3\cdot6)\equiv(0,4,5)\pmod{7}.

Since {0,4,5}=4+{0,1,3}\{0,4,5\}=4+\{0,1,3\}, the residue b13=0b_{13}=0 belongs to R13+R_{13}^{+}. The other entries are obtained by the same six-bit calculation, as verified in Appendix § 8.

Notice that the seven residues bcb_c in Table 4 are not independent: by (22), all depend on the same pair (θ,ρ)(\theta,\rho). This dependence drives the elimination.

Elimination of the nonboundary carry states

We first assume that

cθ∉Zfor every c∈C.(29)c\theta\notin\mathbb{Z}\quad\text{for every }c\in C. \tag*{(29)}

Equivalently, θ\theta is not any breakpoint j/cj/c with 0≤j≤c0\leq j\leq c and c∈Cc\in C. Hence all seven sums under consideration are trinomials, so Table 4 applies without exception.

Deriving the four surviving regions

Since 0≤θ<10 \le\theta< 1, we have k1=0k_{1}=0, and therefore

b1≡ρ−1,b3≡3ρ−43k3−1,b5≡5ρ−43k5−1(mod64).(30)b_{1} \equiv\rho- 1,\qquad b_{3} \equiv3\rho- 43k_{3} - 1,\qquad b_{5} \equiv5\rho- 43k_{5} - 1 \pmod{64}. \tag*{(30)}

The c=1c=1 row of Table 4 gives

ρ≡{2(mod4),type +,1(mod4),type −.(31)\rho\equiv \begin{cases} 2 \pmod{4}, & \text{type }+,\\ 1 \pmod{4}, & \text{type }-. \end{cases} \tag*{(31)}

Now k3=⌊3θ⌋∈{0,1,2}k_{3}=\lfloor3\theta\rfloor\in\{0,1,2\}. For c=3c=3 only reduction modulo 16 is needed, and 43≡11(mod16)43 \equiv11 \pmod{16} gives

b3≡3ρ−11k3−1(mod16).b_{3} \equiv3\rho- 11k_{3} - 1 \pmod{16}.

Checking ρ=2,6,10,14(mod16)\rho=2,6,10,14 \pmod{16} for type ++ and ρ=1,5,9,13(mod16)\rho=1,5,9,13 \pmod{16} for type −- yields:

To illustrate: for type ++ and k3=1k_{3}=1, the four possible values ρ≡2,6,10,14(mod16)\rho\equiv2,6,10,14 \pmod{16} give 3ρ−12≡10,6,2,14(mod16)3\rho-12 \equiv10,6,2,14 \pmod{16}. Only 10 lies in {10,11,12}\{10,11,12\}, so ρ≡2(mod16)\rho\equiv2 \pmod{16}.

Next k5=⌊5θ⌋k_{5}=\lfloor5\theta\rfloor, where k5=jk_{5}=j corresponds to the open interval (j/5,(j+1)/5)(j/5,(j+1)/5). The c=5c=5 condition is

b5≡5ρ−11k5−1(mod16),{b5∈{10,12,14},type +,b5∈{11,13,15},type −.(32)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} \tag*{(32)}

For each of the four nonempty entries in Table 5, testing the compatible k5k_{5}’s leaves just the rows below. The displayed b5b_{5} values are reduced modulo 16.

k3k_{3}interval for θ\thetatype ++: ρ\rho (mod 16)type −-: ρ\rho (mod 16)
0(0,13)(0,\frac{1}{3})none5
1(13,23)(\frac{1}{3},\frac{2}{3})29
2(23,1)(\frac{2}{3},1)6none

Table 5. Survivors after imposing c=1,3c=1,3; an empty entry means no residue survives.

For example, in the first row, ρ≡2(mod16)\rho\equiv2 \pmod{16} gives b5≡9−11k5(mod16)b_{5}\equiv9-11k_{5}\pmod{16}. Of the compatible values k5=1,2,3k_{5}=1,2,3, only k5=1k_{5}=1 gives a permitted type ++ residue (14), and

(13,23)∩(15,25)=(13,25).\left(\frac{1}{3},\frac{2}{3}\right)\cap\left(\frac{1}{5},\frac{2}{5}\right)=\left(\frac{1}{3},\frac{2}{5}\right).

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 6 is precisely the following table.

Typek3k_{3}k5k_{5}interval for θ\thetaρ\rho (mod 16)b5b_{5} (mod 16)
++11(13,25)(\frac{1}{3},\frac{2}{5})214
++23(23,45)(\frac{2}{3},\frac{4}{5})612
−-01(15,13)(\frac{1}{5},\frac{1}{3})513
−-13(35,23)(\frac{3}{5},\frac{2}{3})911

Table 6. All survivors after c=1,3,5c=1,3,5: the carry indices and resulting intervals.

Typeinterval for θ\thetapossible ρ\rho (mod 64)
++(13,25)(\frac{1}{3},\frac{2}{5}){2,18,34,50}\{2,18,34,50\}
++(23,45)(\frac{2}{3},\frac{4}{5}){6,22,38,54}\{6,22,38,54\}
−-(15,13)(\frac{1}{5},\frac{1}{3}){5,21,37,53}\{5,21,37,53\}
−-(35,23)(\frac{3}{5},\frac{2}{3}){9,25,41,57}\{9,25,41,57\}

Table 7. The four nonboundary states after c=1,3,5c=1,3,5.

We now eliminate these four regions. Each numerical residue below is obtained from (22), and the permissible residues are given in Table 4.

Eliminating the type-plus regions

First region: 1/3<θ<2/51/3 < \theta< 2/5. Here k7=⌊7θ⌋=2k_7 = \lfloor7\theta\rfloor= 2 and ρ∈{2,18,34,50}\rho\in\{2,18,34,50\}. The four values of b7b_7 (mod 32) are

ρ2183450b7 (mod⁡32)237237\begin{array}{c|cccc} \rho& 2 & 18 & 34 & 50 \\ b_7\ (\operatorname{mod} 32) & 23 & 7 & 23 & 7 \end{array}

But the type + row for c=7c = 7 allows only {9,16,18,19}\{9,16,18,19\} (mod 32), so this region is empty.

Second region: 2/3<θ<4/52/3 < \theta< 4/5. Initially ρ∈{6,22,38,54}\rho\in\{6,22,38,54\}. The carry k7k_7 changes at θ=5/7\theta= 5/7. If 2/3<θ<5/72/3 < \theta< 5/7, then k7=4k_7 = 4, and

(b7mod⁡32)ρ=6,22,38,54=(29,13,29,13).(b_7 \operatorname{mod} 32)_{\rho=6,22,38,54} = (29,13,29,13).

None is permitted, so this subinterval is empty.

For 5/7<θ<4/55/7 < \theta< 4/5, one has k7=5k_7 = 5, giving

\begin{array}{c|cccc} \rho& 6 & 22 & 38 & 54 \\ b_7\ (\operatorname{mod} 32) & 18 & 2 & 18 & 2 \end{array} \qquad\Longrightarrow\qquad\rho\in\{6,38\}. \tag*{(33)}\end{array}

The next carry k9k_9 changes at θ=7/9\theta= 7/9. For 5/7<θ<7/95/7 < \theta< 7/9, k9=6k_9 = 6 and

(b9mod⁡32)ρ=6,38=(19,19),(b_9 \operatorname{mod} 32)_{\rho=6,38} = (19,19),

which is permitted for both residues. For 7/9<θ<4/57/9 < \theta< 4/5, k9=7k_9 = 7 and the two values are (8,8)(8,8) (mod 32), so both are excluded.

It remains to treat 5/7<θ<7/95/7 < \theta< 7/9. The carry k11k_{11} changes at θ=8/11\theta= 8/11:

(a) If 5/7<θ<8/115/7 < \theta< 8/11, then k11=7k_{11} = 7. For ρ=6,38\rho= 6,38 formula (4.3) gives (b11mod⁡64)=(20,52)(b_{11} \operatorname{mod} 64) = (20,52), outside R11+={32,…,41}R_{11}^{+} = \{32,\ldots,41\}. Hence this interval is empty.

(b) If 8/11<θ<7/98/11 < \theta< 7/9, then k11=8k_{11} = 8, giving (b11mod⁡64)=(41,9)(b_{11} \operatorname{mod} 64) = (41,9). This keeps only ρ=6\rho= 6. Here k13=9k_{13} = 9 or 10, depending on whether θ<10/13\theta< 10/13 or θ>10/13\theta> 10/13. In either case,

b13≡13⋅6−43k13−1≡{10,k13=9,31,k13=10(mod64).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 R13+={0,8,13,15,38,49,58,60}R_{13}^{+} = \{0,8,13,15,38,49,58,60\}. Thus this interval is empty as well.

We conclude that both type + regions are impossible.

Eliminating the type-minus regions

First region: 1/5<θ<1/31/5 < \theta< 1/3. Initially ρ∈{5,21,37,53}\rho\in\{5,21,37,53\}. The carry k7k_7 changes at 2/72/7. If 2/7<θ<1/32/7 < \theta< 1/3, then k7=2k_7 = 2 and

(b7mod⁡32)ρ=5,21,37,53=(12,28,12,28),(b_7 \operatorname{mod} 32)_{\rho=5,21,37,53} = (12,28,12,28),

none of which is permitted by R7−={0,22,23,25}+32Z64R_7^{-} = \{0,22,23,25\} + 32\mathbb{Z}_{64}. If 1/5<θ<2/71/5 < \theta< 2/7, then k7=1k_7 = 1 and

(b7mod⁡32)ρ=5,21,37,53=(23,7,23,7),ρ∈{5,37}.(b_7 \operatorname{mod} 32)_{\rho=5,21,37,53} = (23,7,23,7), \qquad\rho\in\{5,37\}.

The carry k9k_9 changes at 2/92/9. For 1/5<θ<2/91/5 < \theta< 2/9, one has k9=1k_9 = 1 and (b9mod⁡32)ρ=5,37=(1,1)(b_9 \operatorname{mod} 32)_{\rho=5,37} = (1,1), which is outside the permitted set {0,2,8,22,25,28,30}\{0,2,8,22,25,28,30\}. Thus there is no solution there. For 2/9<θ<2/72/9 < \theta< 2/7, one has k9=2k_9 = 2 and (b9mod⁡32)ρ=5,37=(22,22)(b_9 \operatorname{mod} 32)_{\rho=5,37} = (22,22), so both remain.

The carry k11k_{11} changes at 3/113/11 inside this interval. If 3/11<θ<2/73/11 < \theta< 2/7, then k11=3k_{11} = 3 and (b11mod⁡64)ρ=5,37=(53,21)(b_{11} \operatorname{mod} 64)_{\rho=5,37} = (53,21), neither of which belongs to R11−={0,1,…,9}R_{11}^{-} = \{0,1,\ldots,9\}. If 2/9<θ<3/112/9 < \theta< 3/11, then k11=2k_{11} = 2 and (b11mod⁡64)ρ=5,37=(32,0)(b_{11} \operatorname{mod} 64)_{\rho=5,37} = (32,0), so only ρ=37\rho= 37 remains. For this last residue,

b13≡13⋅37−43k13−1(mod64).b_{13} \equiv13 \cdot37 - 43k_{13} - 1 \pmod{64}.

Here k13=2k_{13} = 2 or 3, according as θ<3/13\theta< 3/13 or θ>3/13\theta> 3/13; consequently

b13≡10 or 31(mod64).b_{13} \equiv10 \text{ or } 31 \pmod{64}.

Neither value lies in R13−={3,26,28,33,41,45,47,56}R_{13}^{-} = \{3,26,28,33,41,45,47,56\}. Hence the first type − region is impossible.

Second region: 3/5<θ<2/33/5 < \theta< 2/3. Here k7=4k_7 = 4 and ρ∈{9,25,41,57}\rho\in\{9, 25, 41, 57\}. The values of b7b_7 (mod 32) are (18, 2, 18, 2), none of which lies in {0,22,23,25}\{0, 22, 23, 25\}. This last region is therefore empty.

We have proved the following conclusion.

Proposition 5.1 (No nonboundary seventh-root solutions). Under (5.1), it is impossible for all seven sums (1.2) to vanish at a primitive seventh root of either type.

Elimination of the boundary carry states

The previous section assumed that every cθc\theta was nonintegral. We now remove that restriction. Suppose that

θ=xM=jd∈[0,1)(34)\theta= \frac{x}{M} = \frac{j}{d} \in[0,1) \tag*{(34)}

is a breakpoint in lowest terms. Because dx=jMdx = jM and gcd⁡(j,d)=1\gcd(j,d) = 1, Euclid’s lemma gives d∣Md \mid M. Since the breakpoint is j′/cj'/c for some c∈Cc \in C, the reduced denominator dd also divides one of the integers in CC. Therefore

d∈{1,3,5,7,9,11,13}.d \in\{1,3,5,7,9,11,13\}.

Lemma 6.1 (Possible breakpoint denominators). Under the hypotheses m≥9m \ge9 odd and 3∣m3 \mid m, any breakpoint that can arise from x/Mx/M has reduced denominator

d∈{1,3,9,11}.(35)d \in\{1,3,9,11\}. \tag*{(35)}

Proof. If d∣Md \mid M, then 2m=3M−1≡−1(modd)2^m = 3M - 1 \equiv-1 \pmod d. For d=5d = 5, the multiplicative order of 22 (mod 5) is 4, and 2m=−12^m = -1 (mod 5) would require m≡2m \equiv2 (mod 4), contrary to mm odd. For d=7d = 7, the powers of 2 are 1,2,41,2,4 (mod 7) and never −1-1. For d=13d = 13, the order of 2 is 12 and 26≡−12^6 \equiv-1 (mod 13); thus 2m≡−12^m \equiv-1 (mod 13) would require m≡6m \equiv6 (mod 12), again impossible for odd mm. Consequently d∉{5,7,13}d \notin\{5,7,13\}, proving (6.2). □

The boundary residue ρ\rho is determined

For d∈{1,3,9,11}d \in\{1,3,9,11\}, the integer dd is odd and therefore invertible modulo 64. Reducing dx=jMdx = jM modulo 64 gives

ρ≡43jd−1(mod64).(36)\rho\equiv43j d^{-1} \pmod{64}. \tag*{(36)}

The inverses for d=1,3,9,11d = 1,3,9,11 are 1, 43, 57, 35, respectively. For example, θ=2/9\theta= 2/9 gives ρ≡43⋅2⋅57≡38(mod64)\rho\equiv43 \cdot2 \cdot57 \equiv38 \pmod{64}.

For θ>0\theta> 0 we have c=1c = 1 in the trinomial case, and thus Table 4 imposes

ρ≡{2(mod4),type +,1(mod4),type −.(37)\rho\equiv \begin{cases} 2 \pmod{4}, & \text{type }+,\\ 1 \pmod{4}, & \text{type }-. \end{cases} \tag*{(37)}

Using (6.3), this produces the short list in Table 8. For instance, when d=11d = 11, equation (6.3) becomes ρ≡33j(mod64)\rho\equiv33j \pmod{64}, hence ρ≡j(mod4)\rho\equiv j \pmod{4}. For type ++ this allows j=2,6,10j = 2,6,10; for type −- it allows j=1,5,9j = 1,5,9. The cases d=3d = 3 and d=9d = 9 are just as elementary.

Typeθ\thetaρ\rhoc=3c=3 value
+00binomial: B3≡42B_3 \equiv42
+2/112/112b3≡5b_3 \equiv5
+2/92/938b3≡49b_3 \equiv49
+6/116/116b3≡38b_3 \equiv38
+2/32/350binomial: B3≡42B_3 \equiv42
+10/1110/1110b3≡7b_3 \equiv7
−00binomial: B3≡42B_3 \equiv42
−1/111/1133b3≡34b_3 \equiv34
−1/31/357binomial: B3≡42B_3 \equiv42
−5/115/1137b3≡3b_3 \equiv3
−7/97/95b3≡56b_3 \equiv56
−9/119/1141b3≡36b_3 \equiv36

Table 8. All boundary states surviving c=1c=1, and their c=3c=3 data. For a trinomial entry, b3b_3 is shown modulo 64.

The point θ=0\theta= 0 needs a special comment: then x=0x = 0, and Sr,2(y)=y−6+y=0S_{r,2}(y) = y^{-6} + y = 0 for any primitive seventh root yy. Thus it survives the first filter for both types, despite being binomial rather than trinomial.

Excluding the remaining boundary states with c=3c = 3

For every trinomial entry in Table 8, one has k3=⌊3θ⌋k_3 = \lfloor3\theta\rfloor and b3≡3ρ−43k3−1(mod64)b_3 \equiv3\rho- 43k_3 - 1 \pmod{64}. The four type ++ entries give

b3≡5,49,38,7(mod64),b3 mod 16∈{5,1,6,7},b_3 \equiv5,49,38,7 \pmod{64}, \qquad b_3 \bmod16 \in\{5,1,6,7\},

whereas R3+R_3^+ requires b3 mod 16∈{10,11,12}b_3 \bmod16 \in\{10,11,12\}. Likewise, the four type −- entries give

b3≡34,3,56,36(mod64),b3 mod 16∈{2,3,8,4},b_3 \equiv34,3,56,36 \pmod{64}, \qquad b_3 \bmod16 \in\{2,3,8,4\},

whereas R3−R_3^- requires {13,14,15}\{13,14,15\} (mod 16). Thus all eight trinomial entries are excluded.

The only remaining distinct boundary values are θ=0,1/3,2/3\theta= 0,1/3,2/3, for which 3θ∈Z3\theta\in\mathbb{Z}. The corresponding c=3c = 3 sums are binomials with

B3≡42(mod64),B3+M≡21(mod64).B_3 \equiv42 \pmod{64}, \qquad B_3 + M \equiv21 \pmod{64}.

Since α3=8\alpha_3=8, the two Lucas indices are

i0=8&42=8,i1=8&21=0.i_0=8\mathbin{\&}42=8,\qquad i_1=8\mathbin{\&}21=0.

Thus the exponents are −24-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=0y^{-24}+y=0 would imply y25=1y^{25}=1, incompatible with ord⁡(y)=7\operatorname{ord}(y)=7.

Proposition 6.2 (No boundary seventh-root solutions). No breakpoint θ=x/M\theta=x/M can satisfy all seven vanishing conditions (1.2) at a primitive seventh root of either type.

Proof of the theorems

Proof of Theorem 1.2. Assume (1.2). Suppose, for contradiction, that y3≠1y^3\ne1. Lemma 3.1 then forces yy to have order 7 and to be of type + or type −. The number θ=x/M\theta=x/M is either a breakpoint or is not. Proposition 5.1 rules out the nonboundary case; Proposition 6.2 rules out the boundary case. Both possibilities give a contradiction. Therefore y3=1y^3=1. □

Proof of Theorem 1.1. The hypotheses of Theorem 1.1 include the seven indices in (1.2). Apply Theorem 1.2. □

Remark 7.1. For m≥9m\ge9, the only congruence about MM needed for the final elimination is M≡43(mod64)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.

Appendix A. Reproducible finite certificates in SageMath

For completeness, the short SageMath code below verifies Tables 3 and 4, 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.

The 24 polynomial gcds

R.<Y> = 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)

The six-bit residue table and all carry states

The predicate zero uses Lemma 4.1 for three terms and equality of the two exponent classes for two terms. The last loops cover all the breakpoints j/cj/c, all the open intervals between consecutive breakpoints, and both root types.

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.')

References

References

  1. [1]Z. Tu, X. Zeng, Y. Jiang and Y. Li, Binomial permutations over finite fields with even characteristic, Designs, Codes and Cryptography 89 (2021), 2869–2888, https://doi.org/10.1007/s10623-021-00959-4.

Paper details

vlnc:W_tmjnpdeq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents