Arithmetic reconstruction and error recovery from three quadratic traces
Version 1 / Oct 20, 2026 / CC BY 4.0
Abstract
We study completely multiplicative sign functions through their values at positive integers of the forms , and , with observed indices . First occurrences of prime factors give a canonical information set and a complete, prefix-compatible family of parity relations, each involving at most readings. These relations yield exact bounded-distance repair, including corrupted information coordinates, in time for errors; erasures enter through an explicit rank parameter. We then construct arithmetic redundancy without estimating a quadratic regulator. If and , the three traces contain at least negative readings for every fixed and sufficiently large , uniformly in the prime and all other prime signs. The same number of each sign occurs on one trace between and , for each fixed . The proof combines short reconstruction certificates, Lehmer divisibility and balanced divisors. Coprime blocks give compact access to these families without factoring large recurrence terms. Under independent reading noise with fixed erasure probability and conditional flip probability , every source prefix , for fixed , is recoverable from readings with polynomially small failure probability in and preparation polynomial in the numerical and . A fixed positive erasure rate nevertheless leaves exponentially many assignments of observed large-prime signs. No positive-density inverse for unrestricted sources is asserted.
Provenance statement
References
- M. Bardestani and T. Freiberg. Mertens's theorem for splitting primes and more---a concise and adaptable proof of Hardy . arXiv:1309.7482v1, 2013. https://arxiv.org/abs/1309.7482v1. Theorem 3.3 and the following fixed-modulus error estimate.arXiv
- D. J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms , 54 0 (1): 0 1--30, 2005. https://cr.yp.to/coprimes.html. Context for coprime refinement; no complexity bound from this article is used.link
- Y. Bilu, G. Hanrot, and P. M. Voutier. Existence of primitive divisors of Lucas and Lehmer numbers. Journal für die reine und angewandte Mathematik , 539: 0 75--122, 2001. 10.1515/crll.2001.080. With an appendix by M. Mignotte. Definitions in Section 1, Theorem A (Carmichael--Ward), and Theorem 1.4.DOI
- P. Borwein, S. K. K. Choi, and H. Ganguli. Sign changes of the Liouville function on quadratics. Canadian Mathematical Bulletin , 56 0 (2): 0 251--257, 2013. 10.4153/CMB-2011-166-9. https://arxiv.org/abs/1109.3107v1. Theorem 2.2 of arXiv:1109.3107v1.arXivDOI
- K. Conrad. Pell's equation, I . Expository notes, n.d. https://kconrad.math.uconn.edu/blurbs/ugradnumthy/pelleqn1.pdf. Theorem 2.3 (Lagrange), and Sections 4--7. Accessed 27 September 2026.link
- R. de la Bret è che, V. Y. Wang, and M. W. Xu. Random multiplicative functions and making squares from polynomial values. arXiv:2607.06398v1, 2026. https://arxiv.org/abs/2607.06398v1. Introduction and Sections 5--7; contextual comparison, not a proof input.arXiv
- G. Everest, S. Stevens, D. Tamsett, and T. Ward. Primes generated by recurrence sequences. The American Mathematical Monthly , 114 0 (5): 0 417--431, 2007. 10.1080/00029890.2007.11920430. https://arxiv.org/abs/math/0412079v2. Locators refer to arXiv:math/0412079v2: Lemma 4.1, Proposition 4.2 and Theorem 5.1.arXivDOI
- O. Gorodetsky. A Kubilius model for sieve-theoretic sequences. Analysis Mathematica , 2026. 10.1007/s10476-026-00178-w. https://arxiv.org/abs/2608.14190v1. Published online 14 August 2026. The valuation-comparison locator is Theorem 2.3 of arXiv:2608.14190v1.arXivDOI
- R. W. Hamming. Error detecting and error correcting codes. Bell System Technical Journal , 29 0 (2): 0 147--160, 1950. 10.1002/j.1538-7305.1950.tb00463.x.DOI
- W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58 0 (301): 0 13--30, 1963. 10.1080/01621459.1963.10500830.DOI
Show all 16 referencesShow fewer references
- L. M é rai, I. E. Shparlinski, and A. Winterhof. Character sums over sparse elements of finite fields. Bulletin of the London Mathematical Society , 56 0 (4): 0 1488--1510, 2024. 10.1112/blms.13008. https://arxiv.org/abs/2211.08452v1. The locator is Lemma 3.1 of arXiv:2211.08452v1, used only as a stated form of the classical mixed Weil bound.arXivDOI
- M. Mine. An upper bound for the number of smooth values of a polynomial and its applications. arXiv:2410.09558v2, 2025. https://arxiv.org/abs/2410.09558v2. Revised 8 October 2025. Section 1.3, Theorem 1.4 and Corollary 1.5; contextual comparison.arXiv
- NIST . Digital library of mathematical functions. Sections 27.9, 27.11 and 27.12, n.d. https://dlmf.nist.gov/27. Quadratic characters and fixed-modulus prime estimates, in particular Eq. 27.12.8. Accessed 28 September 2026.link
- A. Srinivasan. Infinitely many sign changes of the Liouville function on . Proceedings of the American Mathematical Society , 150 0 (9): 0 3799--3809, 2022. 10.1090/proc/15939. https://arxiv.org/abs/2104.15004v2. Theorem 1.3 of arXiv:2104.15004v2.arXivDOI
- A. V. Sutherland. The analytic class number formula. MIT 18.785 Number Theory I, Lecture 19, 2017. https://math.mit.edu/classes/18.785/2017fa/LectureNotes19.pdf. Theorems 19.12 and 19.15, Fall 2017 lecture notes.link
- J. Ter ä v ä inen. On the Liouville function at polynomial arguments. American Journal of Mathematics , 146 0 (4): 0 1115--1167, 2024. 10.1353/ajm.2024.a932436. https://arxiv.org/abs/2010.07924v4. Locators refer to arXiv:2010.07924v4: Definition 2.8, Theorem 2.9, Proposition 2.10 and Section 6.arXivDOI
Version history
- v1 · 41 pagesSubmitted by Brice PoulyInitial depositCurrentOct 18, 2026