HEXAGONbeta

Local freedom and capacity barriers in quadratic trace reconstruction

Primarily AI-generated textHuman understanding: no partsmath.NT — Number Theorymath.CO — Combinatorics

Contributed by Brice Pouly ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

A completely multiplicative sign function is determined by its values on n2+1n^2+1, n2+2n^2+2, and n2−2n^2-2, 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 HN=No(1)H_N=N^{o(1)}, one table with o(N)o(N) negative entries passes every HNH_N-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 pp 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 Q(p)\mathbb{Q}(\sqrt p). Conversely, selected values of n2+1n^2+1 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 Pack⁡=3<Cap⁡=4<μ=5\operatorname{Pack}=3<\operatorname{Cap}=4<\mu=5. The selected-sample constructions do not give an upper bound for the minimum on a complete prefix.

Provenance statement

The following declaration describes the research and the published source edition: GPT-6 Astra assisted the research development, calculations, proof drafting, source consultation, and preparation of the original manuscript and checker. GPT-6 Astra Pro assisted the reviews and revisions, including bibliographic cross-checks, proof exposition, and reproducibility packaging. The revision history is recorded in the source archive. The supplied reviews are AI reports, not human mathematical endorsements. The finite checker has been rerun for this edition; no Lean formalisation or independent human verification is claimed. The author is responsible for the submitted manuscript. Computational agreement concerns only the explicit finite objects and does not certify originality or the external theorems used in the proofs. For this Hexagon deposit, OpenAI Codex assisted source packaging, compilation checks and the preparation of submission metadata. This preparation does not constitute independent mathematical peer review. The published edition used for this deposit, including its supplementary source material, is available at https://doi.org/10.5281/zenodo.23319030. At the time of preparation for Hexagon, the submitter declares the text primarily AI-generated and declares that no part of the contribution has been checked and understood by a human.

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  1. 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
  2. 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
  3. J.-H. Evertse and J. H. Silverman. Uniform bounds for the number of solutions to Yn=f(X)Y^n=f(X). 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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

  1. v1Submitted by Brice PoulyInitial depositCurrentOct 18, 2026