We give a deterministic polynomial-time primality test whose main
verification is the congruence $(1+X)^n=1+X^n$ in
$C_n[X]/(X^r-b(Y))$, where
$C_n=(\Z/n\Z)[Y]/(\Phi_r(Y))$. Two identities in the coefficient
ring normalize $b$ and ensure compatibility with the main congruence.
A finite-field root count and a lattice bound show that an accepted
input is a prime power; elementary preprocessing excludes nontrivial
perfect powers. We construct $b$ deterministically using Jacobi sums
and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner,
which extends OpenAI's Hecke zero-free theorem. The total bit complexity
is $L^{32+o(1)}$, where $L=\lceil\log_2 n\rceil$, and verification
after constructing $b$ costs $L^{6+o(1)}$. We also
state a fixed-base modification of Agrawal's conjecture, using the
modulus $X^r-2$ with $r$ the least positive integer not dividing
$n(n-1)$.
Substantially rewritten and retitled. The earlier unproved correctness claim is replaced by a theorem establishing a deterministic polynomial-time variant of the binomial-congruence test. The revision includes a Jacobi-sum parameter construction using recent uniform zero-free estimates, a correctness proof building on Bernstein's algebraic framework, and a worst-case bit-complexity analysis. The original fixed-base test is retained as an open conjecture.
A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. Central to our test is a novel polynomial reduction ring, applied to efficiently validate the polynomial congruence $(1 + x)^n \equiv 1 + x^n \pmod{n}$, a condition that holds exclusively for prime $n$. The test is grounded in our main theorem, supported by a series of lemmas, which collectively show how the congruence is verified through polynomial expansion within our reduction ring.
Clarify test conditions. Revise main theorem and its proof. Add new supporting identities and lemmas. Update presentation.
A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. The test posits that an integer $n$ satisfying the conditions of the main theorem is prime. Combining elements of number theory and combinatorics, the proof operates on the basis of simultaneous modular congruences relating to binomial transforms of powers of two.
The argument with X,Y,Z (bottom of page 4 and top of 5) does not make much sense. I believe the proof is wrong.
Pavel, thank you for reading my paper. I do agree that part of the proof is flawed. I was attempting to say that the sums are linearly independent modulo $n$, but in hindsight, my argument doesn't make much sense. I am working on revisions now and I will post them as soon as I can. Please share any other feedback or questions you have.
Dear eccc community,
Recent developments have brought to my attention the possibility of overlap with existing conjectures within the field. Additionally, there are concerns that some of the assumptions made in my proofs may not be robust enough to fully support the conclusions drawn. I am in the process of conducting a thorough review to understand the extent of these overlaps and their implications on the originality and validity of my work. This review is being undertaken with a commitment to maintaining the integrity and accuracy of the academic record.
Further details will be provided as soon as a more definitive assessment is available.
I appreciate your understanding and patience during this time.
Sincerely,
Joseph M. Shunia
I would like to provide an update to the ECCC community. Following my previous comment, I am undertaking a thorough re-evaluation of the paper.
This re-evaluation is focused on ensuring that all assumptions made in the paper are clearly stated and that any reliance on existing conjectures or non-standard premises is explicitly acknowledged and justified. I understand the critical importance of clarity and precision in outlining the assumptions, and the relationship of my work to established conjectures and theories in the field.
Should this process reveal that these concerns cannot be satisfactorily resolved, I am prepared to retract the paper.
I appreciate the community's patience and understanding as I navigate through this process, and I will provide further updates as they become available.
Revision 2 is now available under the new title "Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence".
The revision replaces the earlier argument with a modified test, including a deterministic parameter construction, a correctness proof, and a worst-case polynomial-time complexity analysis. The original fixed-base test is retained as an open conjecture.
This revision supersedes the claims and arguments in the earlier versions.
