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
In their study of the permutation property of (1), Tu, Zeng, Jiang and Li [1] reduced the remaining necessity question, for odd and divisible by , to the simultaneous vanishing of certain sums , where . They posed the following assertion as Conjecture 1 of [1]. We state it for arbitrary nonzero , which is the form useful below.
Theorem 1.1 (Conjecture 1 of Tu–Zeng–Jiang–Li). Let
and let and . If
then .
The proof below establishes the following stronger version.
Theorem 1.2 (Seven-index strengthening). Under the assumptions on , , in Theorem 1.1, if
then .
The point is that the conclusion is uniform in and . Since is odd and divisible by , necessarily . Thus all seven indices in (2) belong to the range .
We proceed as follows. Section 2 derives an exact two- or three-term formula from the original sums. Section 3 explains why 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
For with , define the integer interval
and let be the least integer for which . Following equation (6) of [1], set
The reduced sum is
where or according as contains two or three multiples of . We interpret a binomial coefficient with an out-of-range lower argument as zero and work in characteristic two.
For the chosen indices, write
Choose uniquely by
and for each write
The following exact computation is the basis of the proof.
Lemma 2.1 (Exact value of ). For every such that , one has
and
Thus has two terms exactly when .
Proof. Write with . Since , the upper endpoint of is
Also , so dividing the entire interval by gives
An integer multiple of in corresponds precisely to an integer multiple of in (2.10). Using , the latter interval is
If , its only multiples of are and . If , its only multiples of are , and . (The endpoint inequalities are inclusive; this is why the case must be treated separately.) It follows that
Substitution in (2.3), with
gives for and otherwise. The lists of multiples give (11) as well. □
Why the binomial sum has exactly one Lucas term per layer
For nonnegative integers , let denote their bitwise binary AND. For example, and , so .
Lemma 2.2 (Unique Lucas contribution). Let . Exactly one integer gives a nonzero product in
namely
Consequently,
Proof. Write and in binary positions. Because has all positions equal to , and have complementary binary supports. Lucas’s theorem says that is odd precisely when every 1-bit of is in the support of . Similarly, is odd precisely when every 1-bit of is in the complementary support. There can be no binary carry between these disjoint supports; hence is the disjoint splitting of the 1-bits of into the two complementary supports. It is unique, and the first part is exactly .
For , the relevant lower binomial arguments are and . For they are , , . All lie in , since . Thus the unique-term statement applies to each in (6), and yields (2.12). □
The first two indices: reduction to seventh roots
Because , the identity implies
Indeed, for , and modulo , , is , , , respectively.
The four trinomials for
For we have . If , then and
Since , only the bit of value is tested. Using , we obtain the following complete table.
| mod 4 | ||
| 0 | ||
| 1 | ||
| 2 | ||
| 3 |
Table 1. The four possibilities for when .
Write
Since , the vanishing of in the trinomial case is equivalent to for one of these four polynomials.
The six trinomials for alpha=8
For we have . In its trinomial case, put . Since , the value of depends only on (mod 16). One obtains:
Here
For example, if then and
All 24 common factors and the binomial exceptions
Put . Euclid’s algorithm in 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 , one has , whence
and therefore . Hence . Taking reciprocal polynomials shows that . Moreover,
We also need to check the possibility of two-term sums. If is a binomial, then , so is also binomial. Formula (14) gives
Their simultaneous vanishing implies and hence . If is a trinomial but is a binomial, the second equation gives . However, divides , and because is odd,
Thus , so . This is impossible for a three-term sum in characteristic two, since .
We have proved the following key lemma.
Lemma 3.1 (Reduction to seventh roots). If and , then precisely one of
holds. In either case has multiplicative order 7.
Proof. The binomial possibilities have just been excluded. If both sums are trinomials, is a common root of some . Table 3 shows that either or or . The first possibility gives , contrary to the hypothesis. Factoring the latter two polynomials as in (18) gives (19). Each cubic in (19) has no root in and hence is irreducible. Its nonzero roots lie in , 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 , which is incompatible with either cubic. □
Table 3. The 24 gcds over ; .
Fano-plane relations and the six-bit table
Suppose from now on, for contradiction, that all seven sums in (2) vanish but . By Lemma 3.1, is a primitive seventh root. We use the terminology
Reduction to six binary positions
Set
where is always represented by an integer in . For each put . If , then lies in , so (2.8) and (3.1) yield
If , the sum is instead a binomial, with
Since , the binary AND with uses only the lowest six bits of . Thus, in the trinomial case, the exponents may be reduced modulo 7 as
The vanishing condition is exactly
Why the exponent sets are translates of two triples
Lemma 4.1 (The seven additive lines). Let have order 7. For three integers , the equality (25) holds if and only if the residues are distinct and, for some ,
Proof. For type , the defining equation is . Multiplying by gives , which proves sufficiency of the seven translates of . Similarly, type gives the seven translates of .
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 , each unordered pair of distinct nonzero elements uniquely determines the zero-sum triple . There are pairs, and every triple contains three pairs, so there are exactly zero-sum triples. The seven translates above are distinct (a nonzero translation of cannot stabilize a three-element subset), so they exhaust all possibilities. □
:::
For reference, the type + lines are
whereas the type lines are
These are the seven lines of the additive Fano plane of .
Derivation and complete statement of the residue table
For each , let (respectively ) denote the set of residues 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 . For a set , the notation means all residues congruent modulo to some member of .
Here are three hand-checkable examples.
(i) . Here and . For , respectively, the triples are
Thus and .
(ii) . Here and only matters. The six groups of in Table 2 give the exponent triples
| mod 16 | monomial-free polynomial | |
| 0, 1 | ||
| 2, 3, 4 | ||
| 5, 6, 7 | ||
| 8, 9 | ||
| 10, 11, 12 | ||
| 13, 14, 15 |
Table 2. All 16 residues for the trinomial .
Only the fifth group is a type + line: . Only the sixth group is a type line: . This gives the second row of Table 4.
| 1 | ||
| 3 | ||
| 5 | ||
| 7 | ||
| 9 | ||
| 11 | ||
| 13 |
Table 4. Complete permissible trinomial residues (mod 64).
(iii) , one entry. Here . If , the three six-bit inputs are . Their ANDs with 38 are , so
Since , the residue belongs to . The other entries are obtained by the same six-bit calculation, as verified in Appendix § 8.
Notice that the seven residues in Table 4 are not independent: by (22), all depend on the same pair . This dependence drives the elimination.
Elimination of the nonboundary carry states
We first assume that
Equivalently, is not any breakpoint with and . Hence all seven sums under consideration are trinomials, so Table 4 applies without exception.
Deriving the four surviving regions
Since , we have , and therefore
The row of Table 4 gives
Now . For only reduction modulo 16 is needed, and gives
Checking for type and for type yields:
To illustrate: for type and , the four possible values give . Only 10 lies in , so .
Next , where corresponds to the open interval . The condition is
For each of the four nonempty entries in Table 5, testing the compatible ’s leaves just the rows below. The displayed values are reduced modulo 16.
| interval for | type : (mod 16) | type : (mod 16) | |
| 0 | none | 5 | |
| 1 | 2 | 9 | |
| 2 | 6 | none |
Table 5. Survivors after imposing ; an empty entry means no residue survives.
For example, in the first row, gives . Of the compatible values , only gives a permitted type residue (14), and
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.
| Type | interval for | (mod 16) | (mod 16) | ||
| 1 | 1 | 2 | 14 | ||
| 2 | 3 | 6 | 12 | ||
| 0 | 1 | 5 | 13 | ||
| 1 | 3 | 9 | 11 |
Table 6. All survivors after : the carry indices and resulting intervals.
| Type | interval for | possible (mod 64) |
Table 7. The four nonboundary states after .
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: . Here and . The four values of (mod 32) are
But the type + row for allows only (mod 32), so this region is empty.
Second region: . Initially . The carry changes at . If , then , and
None is permitted, so this subinterval is empty.
For , one has , giving
The next carry changes at . For , and
which is permitted for both residues. For , and the two values are (mod 32), so both are excluded.
It remains to treat . The carry changes at :
(a) If , then . For formula (4.3) gives , outside . Hence this interval is empty.
(b) If , then , giving . This keeps only . Here or 10, depending on whether or . In either case,
Neither 10 nor 31 belongs to . Thus this interval is empty as well.
We conclude that both type + regions are impossible.
Eliminating the type-minus regions
First region: . Initially . The carry changes at . If , then and
none of which is permitted by . If , then and
The carry changes at . For , one has and , which is outside the permitted set . Thus there is no solution there. For , one has and , so both remain.
The carry changes at inside this interval. If , then and , neither of which belongs to . If , then and , so only remains. For this last residue,
Here or 3, according as or ; consequently
Neither value lies in . Hence the first type − region is impossible.
Second region: . Here and . The values of (mod 32) are (18, 2, 18, 2), none of which lies in . 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 was nonintegral. We now remove that restriction. Suppose that
is a breakpoint in lowest terms. Because and , Euclid’s lemma gives . Since the breakpoint is for some , the reduced denominator also divides one of the integers in . Therefore
Lemma 6.1 (Possible breakpoint denominators). Under the hypotheses odd and , any breakpoint that can arise from has reduced denominator
Proof. If , then . For , the multiplicative order of (mod 5) is 4, and (mod 5) would require (mod 4), contrary to odd. For , the powers of 2 are (mod 7) and never . For , the order of 2 is 12 and (mod 13); thus (mod 13) would require (mod 12), again impossible for odd . Consequently , proving (6.2). □
The boundary residue is determined
For , the integer is odd and therefore invertible modulo 64. Reducing modulo 64 gives
The inverses for are 1, 43, 57, 35, respectively. For example, gives .
For we have in the trinomial case, and thus Table 4 imposes
Using (6.3), this produces the short list in Table 8. For instance, when , equation (6.3) becomes , hence . For type this allows ; for type it allows . The cases and are just as elementary.
| Type | value | ||
| + | 0 | 0 | binomial: |
| + | 2 | ||
| + | 38 | ||
| + | 6 | ||
| + | 50 | binomial: | |
| + | 10 | ||
| − | 0 | 0 | binomial: |
| − | 33 | ||
| − | 57 | binomial: | |
| − | 37 | ||
| − | 5 | ||
| − | 41 |
Table 8. All boundary states surviving , and their data. For a trinomial entry, is shown modulo 64.
The point needs a special comment: then , and for any primitive seventh root . Thus it survives the first filter for both types, despite being binomial rather than trinomial.
Excluding the remaining boundary states with
For every trinomial entry in Table 8, one has and . The four type entries give
whereas requires . Likewise, the four type entries give
whereas requires (mod 16). Thus all eight trinomial entries are excluded.
The only remaining distinct boundary values are , for which . The corresponding sums are binomials with
Since , the two Lucas indices are
Thus the exponents are 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, would imply , incompatible with .
Proposition 6.2 (No boundary seventh-root solutions). No breakpoint 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 . Lemma 3.1 then forces to have order 7 and to be of type + or type −. The number 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 . □
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 , the only congruence about needed for the final elimination is . 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 , 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]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.