Local freedom and capacity barriers in quadratic trace reconstruction
Version 1 / Oct 20, 2026 / CC BY 4.0
Abstract
A completely multiplicative sign function is determined by its values on , , and , but exact determination does not quantify how many readings detect a negative prime sign. We distinguish three losses of information: partial compatibility tests, geometric restrictions on certificates, and fractional relaxation of signed constraints. After fixing a prime head, we describe the exact fibre of a window and the parity constraints joining two windows. For any fixed head and any sequence , one table with negative entries passes every -window test and every two-reading test. A separate finite table passes these tests without any global source. We bound certificate capacity - fractional packing under unit reading loads - for narrow and binary certificates and for low-degree transport libraries whose links cancel odd prime valuations in pairs. A fixed algebraic curve of certificates for a target prime has at most logarithmic capacity, or capacity at most one when a reading is constant; in the infinite unanchored case its common poles have field . Conversely, selected values of can force linearly many errors while the capacity of all certificates stays bounded. Two internally disjoint pair families compose without loss on their existing readings, whereas sixteen actual values exhibit . The selected-sample constructions do not give an upper bound for the minimum on a complete prefix.
Provenance statement
References
- N. Alon, S. Ganguly, and N. Srivastava. High-girth near-Ramanujan graphs with localized eigenvectors . arXiv:1908.03694v1 (https://arxiv.org/abs/1908.03694v1), 2019. Input: the unmodified starting graph at the beginning of Section 3, attributed there to Lubotzky--Phillips--Sarnak.arXiv
- P. Alvanos, Y. Bilu, and D. Poulakis. Characterizing algebraic curves with infinitely many integral points. International Journal of Number Theory 5 (4) (2009), 585--590. doi:10.1142/S1793042109002274 (https://doi.org/10.1142/S1793042109002274). Locators: arXiv:0907.2097v1 (https://arxiv.org/abs/0907.2097v1), introduction and Theorem 1.2.arXivDOI
- M. Bardestani and T. Freiberg. Mertens's theorem for splitting primes and more (A concise and adaptable proof of Hardy) . arXiv:1309.7482v1 (https://arxiv.org/abs/1309.7482v1), 2013. Theorem 3.3; only fixed-modulus progressions are used.arXiv
- V. Bergelson, J. Kułaga-Przymus, M. Lema ń czyk, and F. K. Richter. Rationally almost periodic sequences, polynomial multiple recurrence and symbolic dynamics. Ergodic Theory and Dynamical Systems 39 (9) (2019), 2332--2383. doi:10.1017/etds.2017.130 (https://doi.org/10.1017/etds.2017.130). Locators: arXiv:1611.08392v2 (https://arxiv.org/abs/1611.08392v2), Theorem 1.7 and Section 3.1.arXivDOI
- R. de la Bretèche, V. Y. Wang, and M. W. Xu. Random Multiplicative Functions and Making Squares from Polynomial Values . arXiv:2607.06398v1 (https://arxiv.org/abs/2607.06398v1), 2026. Lemmas 3.1--3.4, equation (13), and Proposition 5.1.arXiv
- A. E. Brouwer. Hoffman--Singleton graph (https://aeb.win.tue.nl/graphs/Hoffman-Singleton.html). Author's graph notes, pentagon--pentagram construction; accessed 27 September 2026.link
- W. Castryck, R. Cluckers, P. Dittmann, and K. H. Nguyen. The dimension growth conjecture, polynomial in the degree and without logarithmic factors. Algebra & Number Theory 14 (8) (2020), 2261--2294. doi:10.2140/ant.2020.14.2261 (https://doi.org/10.2140/ant.2020.14.2261). Locator: Theorem 3 of arXiv:1904.13109v1 (https://arxiv.org/abs/1904.13109v1).arXivDOI
- J. Chinis and B. Shala. Random Chowla's conjecture for Rademacher multiplicative functions. Transactions of the American Mathematical Society 378 (2025), 8025--8053. doi:10.1090/tran/9457 (https://doi.org/10.1090/tran/9457). Locators: arXiv:2409.05952v2 (https://arxiv.org/abs/2409.05952v2), Lemmas 2.4--2.5 and proof.arXivDOI
- K. Conrad. Pell's Equation, I (https://kconrad.math.uconn.edu/blurbs/ugradnumthy/pelleqn1.pdf). Author's notes, Theorem 2.3 and multiplication of solutions; accessed 27 September 2026.link
- G. Cornuéjols. Combinatorial Optimization: Packing and Covering . CBMS-NSF Regional Conference Series in Applied Mathematics 74, SIAM, 2001. doi:10.1137/1.9780898717105 (https://doi.org/10.1137/1.9780898717105). The port definition is in the author's July 2000 notes (https://www.researchgate.net/publication/245695625_Combinatorial_Optimization_Packing_and_Covering), Section 8.3.1, p. 120; this locator refers to those notes, not the SIAM pagination.DOI
Show all 23 referencesShow fewer references
- C. Delorme and S. Poljak. Laplacian eigenvalues and the maximum cut problem. Mathematical Programming 62 (1993), 557--574. doi:10.1007/BF01585184 (https://doi.org/10.1007/BF01585184).DOI
- J. Edmonds and E. L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming 5 (1973), 88--124. doi:10.1007/BF01580113 (https://doi.org/10.1007/BF01580113). Author-institution record (https://research.ibm.com/publications/matching-euler-tours-and-the-chinese-postman).DOI
- J.-H. Evertse and J. H. Silverman. Uniform bounds for the number of solutions to . Mathematical Proceedings of the Cambridge Philosophical Society 100 (2) (1986), 237--248. doi:10.1017/S0305004100066068 (https://doi.org/10.1017/S0305004100066068). Theorem 1(b); original text in the CWI repository (https://ir.cwi.nl/pub/1788/1788D.pdf).DOI
- M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42 (6) (1995), 1115--1145. doi:10.1145/227683.227684 (https://doi.org/10.1145/227683.227684). Author's copy (https://math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf), Section 4, especially Sections 4.2--4.3.DOI
- D. R. Heath-Brown. The square sieve and consecutive square-free numbers. Mathematische Annalen 266 (3) (1984), 251--259. doi:10.1007/BF01475576 (https://doi.org/10.1007/BF01475576).DOI
- K. S. Kedlaya. Notes on analytic number theory . Chapter 13: The Selberg sieve (https://kskedlaya.org/ant/chap-selberg.html), especially Theorem 13.1 and (13.2.3). Author's online notes; accessed 27 September 2026.link
- F. Lemmermeyer. Higher Descent on Pell Conics. I. From Legendre to Selmer . arXiv:math/0311309 (https://arxiv.org/abs/math/0311309), 2003. Section 5, Proposition 5.3.arXiv
- A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988), 261--277. doi:10.1007/BF02126799 (https://doi.org/10.1007/BF02126799). The specialised starting-graph statement is located in AGS .DOI
- L. Mérai, I. E. Shparlinski, and A. Winterhof. Character sums over sparse elements of finite fields. Bulletin of the London Mathematical Society 56 (4) (2024), 1488--1510. doi:10.1112/blms.13008 (https://doi.org/10.1112/blms.13008). Input: Lemma 3.1 of arXiv:2211.08452v1 (https://arxiv.org/abs/2211.08452v1).arXivDOI
- J. S. Milne. Algebraic Number Theory (https://www.jmilne.org/math/CourseNotes/ANT.pdf). Version 3.08, 19 July 2020. Chapters 3--5, especially Propositions 4.1--4.2.link
- National Institute of Standards and Technology. Digital Library of Mathematical Functions . Section 27.12: Asymptotic formulas---primes (https://dlmf.nist.gov/27.12), equations (27.12.5) and (27.12.8), and the preceding statement of Dirichlet's theorem. Accessed 27 September 2026.link
- B. Pouly. Arithmetic reconstruction and error recovery from three quadratic traces . Zenodo, 2026. doi:10.5281/zenodo.23317860 (https://doi.org/10.5281/zenodo.23317860). Theorems 1.1 and 1.3, and Section 5.DOI
- B. Pouly. Selective normality and algebraic rigidity of multiplicative traces . Zenodo, 2026. doi:10.5281/zenodo.23318326 (https://doi.org/10.5281/zenodo.23318326). Lemma 2.1.DOI
Version history
- v1 · 41 pagesSubmitted by Brice PoulyInitial depositCurrentOct 18, 2026