A New Way to Test if a Number Is Prime

In the paper's words

Primality testing is a prerequisite for RSA key generation, yet current deployments rely on probabilistic algorithms such as Miller–Rabin that admit rare composite “liars”. A deterministic polynomial‑time alternative would eliminate this residual risk and simplify certification. We encode an odd integer N as a p‑adic automorphism γ_NinAut(T_p) of the (p + 1)‑regular Bruhat–Tits tree and examine the spectrum of the combinatorial Laplacian Δ_γ_N on the depth‑D=lceillog_p Nrceil quotient graph.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. For $p=2$, $D=6$, an assumed mean eigenvalue $\mu\approx1.984$ yields a projected gap $\delta=2-\mu\approx0.016$, exceeding a working threshold $0.01$.

   from Abstract

2. Lemma 3.1 exploits this description to bound the depth of vertices under $\gamma_N$.

   from 2. Background and Related Work

3. We use [8] only as qualitative motivation for the conjectured composite bound $\lambda_1\le C/D$ stated in Section 4.4; that bound is a hypothesis of this paper and is not derived from [8] or from any other result stated here.

   from 2. Background and Related Work

4. The algorithm declares $N$ prime iff $\delta_N\gt \delta_{\text{threshold}}$, where we assume $\delta_{\text{threshold}}=0.01$ for illustration.

   from 3.3 Spectral‑gap criterion

5. The adjacency spectrum of the infinite $(p+1)$‑regular tree is the interval $$ \sigma(A)=\bigl[-2\sqrt{p},\,2\sqrt{p}\bigr]. $$ Consequently the Laplacian spectrum lies in $$ \sigma(\Delta)=\bigl[(p+1)-2\sqrt{p},\,(p+1)+2\sqrt{p}\bigr]. $$ For $p=2$, $2\sqrt{p}=2\sqrt{2}\approx2.8284$, so $$ \sigma(\Delta)=[\,0.1716,\;5.8284\,]. $$ The lower endpoint $$ \lambda_{\text{gap}}^{\text{prime}} \;=\;(p+1)-2\sqrt{p} \approx0.17157288 $$ is the universal prime lower bound.

   from 4.2 Spectral interval of the infinite tree

6. Assuming, for illustration, a mean eigenvalue $\mu\approx1.984$ for a depth‑$D=6$ tree with $p=2$, the spectral gap is $$ \delta_{\text{obs}} = 2 - \mu \;\approx\;0.016. $$ We adopt $\delta_{\text{threshold}}=0.01$ as a working constant.

   from 4.3 Assumed mean eigenvalue and observed gap (projection)

How it is done

1. Assuming the exponential‑mixing result of [1] and the branch description of [2], we conjecture a spectral‑gap dichotomy: primes are expected to satisfy $\lambda_1\ge(p\!+\!1)-2\sqrt{p}$, while composites are conjectured to obey $\lambda_1\le C/D$ with an assumed constant $C=2$; neither bound is derived in this paper.

   from Abstract

2. Our contributions are: Encoding Lemma (Section 3).

   from 1. Introduction

3. Lemma 3.1 exploits this description to bound the depth of vertices under $\gamma_N$.

   from 2. Background and Related Work

4. Fix a prime $p$ (we use $p=2$ for concrete calculations).

   from 3.1 Encoding an integer as a tree automorphism

What would falsify it

1. The main claim is falsified if a composite integer $N$ yields a spectral gap $\lambda_1\gt \delta_{\text{threshold}}$ (false positive) or if a prime yields $\lambda_1\langle \delta_{\text{threshold}}$ (false negative).

   from 6.2 Falsifiability

2. If the dichotomy holds, RSA implementations could replace probabilistic tests with a provably correct deterministic step, removing probabilistic error from key generation.

   from Abstract

3. Observation of any composite with $\lambda_1\gt \delta_{\text{threshold}}$ would falsify the main claim.

   from (c) Minimal next experiment

Where the claim stops

1. Assumption Sensitivity Lemma 3.1 (tree invariance) Requires the matrix representation; alternative embeddings could alter the invariant subtree.

   from 6.1 Limitations

2. The numerical values presented in Section 5 are labeled projections based on assumed eigenvalues, and no numerical experiment was performed.

   from 8. Conclusion

3. Future work will focus on optimizing Hecke‑operator implementation, extending the analysis to other primes $p$, and integrating the algorithm into cryptographic libraries.

   from 8. Conclusion

Where to read

1. Abstract157 words · 1 min
2. 1. Introduction194 words · 1 min
3. 2. Background and Related Work395 words · 2 min
4. 3. Methods258 words · 1 min
5. 4. Analysis262 words · 1 min
6. 5. Results172 words · 1 min
7. 6. Discussion206 words · 1 min
8. 7. Practical Implications and Engineering Pathways294 words · 1 min
9. 8. Conclusion135 words · 1 min
10. Version History31 words · 1 min
11. Provenance and AI Involvement225 words · 1 min