Matching works

8 works

math.NT — Number Theory

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

Contributed by yi li

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.

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 16, 202611 pages
PDFView work

cs.SC — Symbolic Computation

Deterministic Polynomial-Time Factorization over Finite Fields

Contributed by Qiyue Tang

Using prime-field factorization and a Dedekind zeta zero-free theorem, we obtain deterministic polynomial-time algorithms for complete factorization over finite fields and for constructing their presentations from their orders.

Author comments: I am posting this manuscript to share the mathematical results themselves. In doing so, I do not seek to assert ownership of the results or claim priority. I welcome anyone interested in checking the arguments or preparing a finished account, and I believe the eventual scholarly credit should go to those who undertake that work.

A mix of human-written and AI-generated textHuman understanding: some parts
Nov 06, 20268 pages
PDFView work

math.NT — Number Theory

The exact multiplicity of the Wilson supercongruence in F_q[t]

Contributed by David Niedbala Giraudin

Let q = p^s with p an odd prime, and let P be a monic irreducible polynomial of degree d >= 2 in F_q[t]. The Wilson analogue F_d = -1 mod P holds for the product F_d of all nonzero polynomials of degree less than d, and Thakur proved that P is a Wilson prime, i.e. F_d = -1 mod P^2, exactly when all exponents of P are congruent to 0 or 1 mod p, in which case the congruence holds modulo P^(p-1). He asked whether it can hold modulo a higher power, and what the exact multiplicities are. Let r be the largest integer such that all exponents of P are congruent to 0 or 1 modulo p^r. We prove that the exact multiplicity m = v_P(F_d + 1) is 1 if r = 0, p^r - 1 if 1 <= r <= s, and q + 1 if r > s. In particular m <= q + 1, and the multiplicity of a Wilson prime in the numerator of the sum over i < d of 1/(t^(q^i) - t) is exactly m - 1. Examples over F_3, F_5 and F_9 show that all regimes occur. A script checks the theorem on all primes of small degree and on these examples.

Primarily AI-generated textHuman understanding: no partsCarlitz factorialHasse derivativesWilson primesfunction fieldspolynomials over finite fieldssupercongruences
Nov 04, 20264 pages
PDFView work

math.NT — Number Theory

Recycled roots under reduction and descent in the Casas-Alvero problem

Contributed by David Niedbala Giraudin

For a Casas-Alvero polynomial ff, the type of ff is one less than the minimal number of roots of ff needed to meet every Hasse derivative H1f,…,Hd−1fH_1f,\dots,H_{d-1}f. We show that the type does not increase under reduction modulo a prime and under the descent from degree npenp^e to degree nn in characteristic pp. Consequently, if no Casas-Alvero polynomial of degree nn and type at most kk exists over F‾p\overline{\mathbb F}_p, then none of degree npenp^e and type at most kk exists in characteristic 00, for every e≥0e\ge 0. For k=2k=2 the hypothesis is equivalent to p∤Nnp\nmid N_n for an explicit integer NnN_n, and we show by a finite computation that Nn≠0N_n\ne0 for 3≤n≤223\le n\le 22 and n=24n=24. In particular there is no counterexample of type at most 22 in degree 2424. This gives infinite families of degrees for which the conjecture is not known and every counterexample has type at least 33: the degrees 5⋅8009e5\cdot 8009^e, the degrees 6pe6p^e for 2121 primes pp that are bad for degree 66, the degrees 7pe7p^e, 8pe8p^e, 9pe9p^e and 10pe10p^e for 1313, 1717, 1616 and 103103 explicit primes pp that are bad for these degrees, and the degrees 20pe20p^e and 24pe24p^e for all primes pp outside a finite set (for 20pe20p^e, including p=231−1p=2^{31}-1). For k=3k=3 we obtain the first degrees in which every counterexample has type at least 44: the degrees 6pe6p^e for p∈{983,1901,51313000813080529}p\in\{983,1901,51313000813080529\}, the degrees 8⋅397e8\cdot397^e, the degrees 9pe9p^e for p∈{613,757}p\in\{613,757\} and the degrees 10pe10p^e for 1313 primes pp.

Primarily AI-generated textHuman understanding: no partsCasas-Alvero conjectureHasse derivativesbad primespolynomials over finite fieldsrecycled rootsreduction modulo presultants
Nov 03, 20267 pages
PDFView work

math.NT — Number Theory

The binary Collatz dynamics of the trinomials x^n+x+1: an independent proof of two conjectures of Gallardo and Rahavandrainy

Contributed by David Niedbala Giraudin

Gallardo and Rahavandrainy studied an analogue of the Collatz map on F_2[x], in which x(x+1) plays the role of 2 and x^2+x+1 that of 3: an odd polynomial A is sent to the odd part of 1+(x^2+x+1)A. They proved that every orbit reaches 1, and conjectured that the orbit of the trinomial x^n+x+1 has length 2^s+1, where s is the largest integer with 2^(s+1) < n, and that for 1 <= t <= s-1 it contains 2^t terms of the same degree. We prove both statements for every n >= 3. They were proved earlier, with a complete Lean 4 formalization, by W. Choi; the proof given here was obtained independently. The proof rests on the identity (x^2+x+1)+x(x+1)=1: it reduces the dynamics to a map from one plateau to the next, characterises the last plateau of any orbit, and shows that along the orbit of x^n+x+1 the plateaus start at the 2^j-th powers of the odd parts of the polynomials x^m(x^2+x+1)+1, the index m following an explicit binary recursion. We also note that a later restatement of the conjecture, with a non-strict inequality, fails exactly when n is a power of 2. A script checks all the statements numerically.

Primarily AI-generated textHuman understanding: no parts
Nov 03, 20266 pages
PDFView work

math.NT — Number Theory

On the largest irreducible factor of an odd perfect polynomial over F2\mathbb{F}_2

Contributed by David Niedbala Giraudin

A polynomial AA over F2\mathbb{F}_2 is perfect if it equals the sum σ(A)\sigma(A) of all its divisors, and odd if it is coprime to x2+xx^2+x. Canaday conjectured in 1941 that 1 is the only odd perfect polynomial. Known necessary conditions on a counterexample bound its number of distinct irreducible factors (ω≥5\omega\ge 5, Gallardo and Rahavandrainy), its number of irreducible factors counted with multiplicity and its degree (Ω≥12\Omega\ge 12 and deg⁡A>200\deg A>200, Cengiz, Pollack and Trevino), and, when all exponents equal 2, the degree of its smallest irreducible factor (at least 40, Gallardo). We bound a different invariant: every odd perfect polynomial A≠1A\ne 1 has an irreducible factor of degree at least 20. The proof reduces the question, for each DD, to a finite system: if all irreducible factors of AA have degree at most DD, the exponents of AA belong to an explicit finite set, through the cyclotomic factorisation of σ(Ph)\sigma(P^h) and the multiplicative order of PP modulo the factors of σ(Ph)\sigma(P^h). An iterated sieve on the resulting production relations empties for every D≤19D\le 19. The computation was carried out twice, by two independent programs, with identical results; the second program is attached as an ancillary file. As a cross-check of the method, the same programs reproduce, by the orbit argument of Gallardo and Rahavandrainy, the exclusion of every prime of degree at most 30 as the smallest factor of a special perfect polynomial, in agreement with the published bounds.

Primarily AI-generated textHuman understanding: no partsCanaday conjecturefinite fieldsperfect polynomialssum of divisors
Nov 03, 20266 pages
PDFView work

math.NT — Number Theory

The invariant cMc_M of Gallardo and Rahavandrainy at Mersenne prime exponents, and the case p=7p=7

Contributed by David Niedbala Giraudin

A Mersenne prime polynomial is an irreducible polynomial over F2\mathbb{F}_2 of the form xa(x+1)b+1x^a(x+1)^b+1 with a,b≥1a,b\ge1. Gallardo and Rahavandrainy conjectured that, apart from two exceptions, σ(M2h)\sigma(M^{2h}) always has an irreducible factor which is not a Mersenne prime. For a prime p≥5p\ge5 they proved it for every MM outside an exceptional set Σp=Σp1∪⋯∪Σp4\Sigma_p=\Sigma_p^1\cup\dots\cup\Sigma_p^4, defined through an integer cMc_M and an odd integer mMm_M read off the leading coefficients of σ(σ(Mp−1))\sigma(\sigma(M^{p-1})), and later they proved it for every Mersenne prime number p≥31p\ge31; their method does not reach p=7p=7. We compute cMc_M exactly when p=2d−1p=2^d-1 is a Mersenne prime number: cM=d+1c_M=d+1 if deg⁡M≠d\deg M\ne d, and cM=dc_M=d if deg⁡M=d\deg M=d. Consequently Σp1\Sigma_p^1 consists of the Mersenne primes of degree dd or d+1d+1, Σp2\Sigma_p^2 is empty, and Σp3\Sigma_p^3, Σp4\Sigma_p^4 are described by mM=deg⁡M−d−1m_M=\deg M-d-1 and mM=deg⁡M−dm_M=\deg M-d respectively. For p=7p=7 this reduces the conjecture to the Mersenne primes MM with mM∈{deg⁡M−4,deg⁡M−3}m_M\in\{\deg M-4,\deg M-3\}. A direct computation shows that σ(M6)\sigma(M^6) has a non-Mersenne irreducible factor for every Mersenne prime MM of degree at most 500500, and that mM≤17m_M\le17 in that range. Hence the conjecture holds whenever 77 divides 2h+12h+1 and deg⁡M≤500\deg M\le500, and a counterexample with 7∣2h+17\mid 2h+1 would need mM≥deg⁡M−4>496m_M\ge\deg M-4>496. A script attached as an ancillary file checks these computations, and reproduces the table of exceptional sets of Gallardo and Rahavandrainy.

Primarily AI-generated textHuman understanding: no partsCyclotomic PolynomialsMersenne prime polynomialsfinite fieldsperfect polynomialssum of divisors
Nov 03, 20264 pages
PDFView work

math.NT — Number Theory

The Welch function is not third-order sum-free

Contributed by Deep Bhattacharjee

Let n=2m+1n=2m+1 be odd and let $\F_{2^n}$ be the field with 2n2^n elements. A function on $\F_{2^n}$ is third-order sum-free when its values over any eight elements forming a three-dimensional affine subspace never add up to zero. The Welch function is the power map x↦x2m+3x\mapsto x^{2^m+3}; it is one of the classical almost perfect nonlinear functions, and Hou and Zhao conjectured that for n≥7n\ge7 it is not third-order sum-free. We prove this. The question comes down to a linearised polynomial g(x,y)g(x,y) in yy whose roots form a vector space Z(x)Z(x) over $\F_2$ containing 11 and xx, and the Welch function fails to be third-order sum-free exactly when Z(x)Z(x) has dimension three for some xx outside $\F_2$. We show that the dimension is always 22 or 33, and that it is 33 if and only if two explicit trace conditions hold: with u=x2mu=x^{2^m}, both $\Tr(1/(x+u))$ and $\Tr(xu/(x+u))$ equal 11. The proof applies the field automorphism z↦z2m+1z\mapsto z^{2^{m+1}}, whose square is the Frobenius map, to turn gg into an additive polynomial of degree eight whose roots always lie in $\F_{2^n}$. Counting the elements that satisfy both trace conditions gives exactly (2n+1−3Kn)/4(2^n+1-3K_n)/4 of them, where KnK_n is the binary Kloosterman sum of $\F_{2^n}$, and Weil's bound ∣Kn∣≤2n/2+1|K_n|\le 2^{n/2+1} makes this count positive for every n≥7n\ge7. The Welch function sums to zero over exactly (2n+1−3Kn)(2n−1)/168(2^n+1-3K_n)(2^n-1)/168 three-dimensional linear subspaces, and the count 2+(2n+1−3Kn)/42+(2^n+1-3K_n)/4 agrees with the numbers that Hou and Zhao computed for n≤15n\le15. Every statement is proved by hand.

A mix of human-written and AI-generated textHuman understanding: some partsKloosterman sumsWelch functionalmost perfect nonlinear functionslinearized polynomialssum-free functions
Oct 22, 20269 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations