Feasibility of primality in bounded arithmetic
Forum of Mathematics, Sigma · 2026 · 14
DOI: 10.1017/fms.2026.10194 ↗Kurz gefasst
Fachartikel in der Zeitschrift Forum of Mathematics, Sigma, online erschienen am 01.04.2026. Verfasst von Raheleh Jalali und 1 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
We prove the correctness of the AKS algorithm [1] within the bounded arithmetic theory $T^{\text {count}}_2$ or, equivalently, the first-order consequences of the theory $\text {VTC}^0$ expanded by the smash function, which we denote by $\text {VTC}^0_2$ . Our approach initially demonstrates the correctness within the theory $S^1_2 + \mathrm {iWPHP}$ augmented by two algebraic axioms and then shows that they are provable in $\text {VTC}^0_2$ . The two axioms are: a generalized version of Fermat’s Little Theorem and an axiom adding a new function symbol which injectively maps roots of polynomials over a definable finite field to numbers bounded by the degree of the given polynomial. To obtain our main result, we also give new formalizations of parts of number theory and algebra: • In $\mathrm {PV}_1$ : We formalize Legendre’s Formula on the prime factorization of $n!$ , key properties of the Combinatorial Number System and the existence of cyclotomic polynomials over the finite fields $\mathbb {Z}/p$ . • In $S^1_2$ : We prove the inequality $\text {lcm}(1,\dots , 2n) \geq 2^n$ . • In $\text {VTC}^0$ : We verify the correctness of the Kung–Sieveking algorithm for polynomial division.
Zitieren
APA
Jalali, R., & Ježil, O. (2026). Feasibility of primality in bounded arithmetic. Forum of Mathematics, Sigma, 14. https://doi.org/10.1017/fms.2026.10194
Vancouver
Jalali R, Ježil O. Feasibility of primality in bounded arithmetic. Forum of Mathematics, Sigma. 2026;14. doi:10.1017/fms.2026.10194
BibTeX
@article{Jalali2026,
author = {Jalali, Raheleh and Ježil, Ondřej},
title = {Feasibility of primality in bounded arithmetic},
journal = {Forum of Mathematics, Sigma},
year = {2026},
volume = {14},
doi = {10.1017/fms.2026.10194}
}
EUVIMED