pith. sign in

arxiv: 2606.04858 · v1 · pith:R4AOB6MSnew · submitted 2026-06-03 · 🧮 math.NT · cs.SC

Integer points close to a transcendental curve: an algorithmic approach

Nicolas Brisebarre , Guillaume Hanrot This is my paper

Pith reviewed 2026-06-28 04:26 UTC · model grok-4.3

classification 🧮 math.NT cs.SC
keywords integer pointstranscendental curvesTable Maker's Dilemmacorrect roundingBombieri-PilaCoppersmith methodbinary128algorithm
0
0 comments X

The pith

An algorithmic approach based on Bombieri-Pila and Coppersmith methods locates integer points near transcendental curves, speeding up solutions to the Table Maker's Dilemma for correct function rounding.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an algorithmic method to identify integer points close to a transcendental curve by building on the Bombieri-Pila theorem and Coppersmith's method. This is applied to the Table Maker's Dilemma, the problem of determining correct rounding for mathematical functions. The authors establish theoretical foundations, prove the algorithms, analyze complexity, and run experiments showing significant speedup over previous approaches. These results indicate that creating correctly rounded mathematical libraries for the binary128 floating-point format becomes practical with much lower computational effort.

Core claim

The authors develop and validate an algorithmic framework that efficiently determines integer points near transcendental curves in the specific setting of the Table Maker's Dilemma, with proven correctness, complexity bounds, and experimental evidence of improved performance that lowers the barrier for high-precision correct rounding.

What carries the argument

The adaptation of Bombieri-Pila bounds combined with Coppersmith's method to reduce the search for integer solutions near the curve, implemented as a practical algorithm for instances arising in correct rounding problems.

If this is right

  • The approach solves Table Maker's Dilemma instances faster than prior methods.
  • Correctly rounded libraries for binary128 become feasible at smaller cost.
  • The algorithms have analyzed complexity that supports their practicality.
  • Direct comparison shows improvement over existing techniques for this problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This method could be adapted to other problems involving Diophantine approximation to transcendental functions.
  • Extensions might allow handling even higher precision formats beyond binary128.
  • Integration into automated software tools could streamline the creation of accurate floating-point libraries.
  • Further theoretical refinements might broaden the class of curves to which the bounds apply without restrictions.

Load-bearing premise

The Bombieri-Pila and Coppersmith-style bounds apply directly and without extra restrictions to the transcendental curves that appear in the Table Maker's Dilemma instances.

What would settle it

A specific Table Maker's Dilemma instance where the new algorithm misses an integer point that is known to exist near the curve or fails to deliver the reported speedup in practice.

read the original abstract

In this article, we propose an algorithmic approach to determine the integer points located near a transcendental curve. This approach is closely related to a celebrated work by Bombieri and Pila and to the so-called Coppersmith's method. We establish the underlying theoretical foundations, prove the algorithms, study their complexity and present practical experiments; we also compare our approach with previously existing ones. From a practical point of view, we focus on an instance of our general problem, called the Table Maker's Dilemma, whose solving makes it possible to evaluate a given function with correct rounding. Our experiments show a significant speedup. In particular, our results show that the development of a correctly rounded mathematical library for the binary128 format is now possible at a much smaller cost than with previously existing approaches.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper proposes an algorithmic approach, building on Bombieri-Pila determinant bounds and Coppersmith-style methods, to locate integer points near transcendental curves. It establishes theoretical foundations, proves the algorithms, analyzes their complexity, and reports practical experiments focused on instances of the Table Maker's Dilemma for correct rounding in floating-point evaluation. The experiments claim significant speedups, suggesting that correctly rounded libraries for binary128 are now feasible at substantially lower cost than prior methods.

Significance. If the invoked Bombieri-Pila and Coppersmith bounds are shown to apply directly to the specific transcendental curves (such as graphs of exp or log) arising in the TMD instances used in the experiments, the work would provide a concrete algorithmic improvement with measurable practical impact on the cost of high-precision correctly rounded libraries.

major comments (1)
  1. [theoretical foundations and experimental sections] The central claim of practical speedup for binary128 TMD instances rests on the applicability of the Bombieri-Pila and Coppersmith bounds to the concrete transcendental curves considered. The abstract states that foundations are established, but the manuscript must explicitly verify (with the required analytic or algebraic conditions) that these bounds hold without extra restrictions for the curves actually used in the reported experiments; otherwise the complexity and experimental claims are not underwritten.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need to make the applicability of the Bombieri-Pila and Coppersmith bounds fully explicit for the concrete curves in the TMD experiments. We address this point below.

read point-by-point responses

  1. Referee: [theoretical foundations and experimental sections] The central claim of practical speedup for binary128 TMD instances rests on the applicability of the Bombieri-Pila and Coppersmith bounds to the concrete transcendental curves considered. The abstract states that foundations are established, but the manuscript must explicitly verify (with the required analytic or algebraic conditions) that these bounds hold without extra restrictions for the curves actually used in the reported experiments; otherwise the complexity and experimental claims are not underwritten.

    Authors: We agree that the manuscript should contain an explicit verification of the analytic conditions for the specific curves (exp, log, etc.) arising in the binary128 TMD instances. Section 2 develops the general Bombieri-Pila determinant bounds and Coppersmith-style lattice reduction for transcendental curves satisfying standard analytic hypotheses (real-analyticity on a compact interval together with a non-vanishing derivative or curvature condition). The curves used in the experiments satisfy these hypotheses on the relevant domains; the general theorems therefore apply directly. To remove any ambiguity, we will add a short dedicated paragraph (or subsection) in the revised theoretical foundations section that recalls the precise hypotheses of the cited Bombieri-Pila and Coppersmith statements and verifies them one-by-one for the exponential and logarithm functions over the intervals appearing in the TMD experiments. This addition will explicitly underwrite the complexity analysis and the reported speedups. We view the change as a clarification rather than a substantive alteration of the results. revision: yes

Circularity Check

0 steps flagged

No circularity: external foundations established independently

full rationale

The paper invokes Bombieri-Pila determinant bounds and Coppersmith methods as external theoretical foundations and states that it establishes its own underlying foundations, proves the algorithms, and studies complexity. No equations or claims reduce a derived quantity to a fitted parameter or self-citation by construction. The central experimental claims rest on algorithmic performance for TMD instances rather than any self-referential definition. This matches the default expectation of a self-contained derivation against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.1-grok · 5654 in / 1083 out tokens · 34044 ms · 2026-06-28T04:26:23.176506+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Aanderaa, L

    S. Aanderaa, L. Kristiansen, and H. K. Ruud. Search for good examples of Hall’s conjecture. Math. Comp., 87(314):2903–2914, 2018

    2018

  2. [2]

    InProceedings of the 30th ACM symposium on Theory of computing (STOC), pages 10–19, 1998

    M.Ajtai.TheShortestVectorProbleminL 2 isNP-hardforRandomizedReductions(Extended Abstract). InProceedings of the 30th ACM symposium on Theory of computing (STOC), pages 10–19, 1998

    1998

  3. [3]

    Akhavi and D

    A. Akhavi and D. Stehlé. Speeding-up Lattice Reduction with Random Projections. In E. S. Laber, C. F. Bornstein, L. T. Nogueira, and L. Faria, editors,LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, Proceedings, volume 4957 ofLecture Notes in Computer Science, pages 293–305. Springer, 2008. 12https://gi...

    2008

  4. [4]

    Bauer and M

    M. Bauer and M. A. Bennett. Applications of the hypergeometric method to the generalized Ramanujan-Nagell equation.Ramanujan J., 6(2):209–270, 2002

    2002

  5. [5]

    Berthé and L

    V. Berthé and L. Imbert. Diophantine approximation, Ostrowski numeration and the double- base number system.Discrete Math. Theor. Comput. Sci., 11(1):153–172, 2009

    2009

  6. [6]

    F. Beukers. On the generalized Ramanujan-Nagell equation. I.Acta Arith., 38(4):389–410, 1980-1981

    1980

  7. [7]

    F. Beukers. On the generalized Ramanujan-Nagell equation. II.Acta Arith., 39(2):113–123, 1981

    1981

  8. [8]

    Bombieri and J

    E. Bombieri and J. Pila. The number of integral points on arcs and ovals.Duke Math. J., 59(2):337–357, 1989

    1989

  9. [9]

    Boneh and G

    D. Boneh and G. Durfee. Cryptanalysis of RSA with private key𝑑 less than 𝑁 0.292.IEEE Trans. Inform. Theory, 46(4):1339–1349, 2000

    2000

  10. [10]

    J. P. Boyd.Chebyshev and Fourier spectral methods. Dover Publications Inc., Mineola, NY, second edition, 2001

    2001

  11. [11]

    Brisebarre and S

    N. Brisebarre and S. Chevillard. Efficient polynomial𝐿∞ approximations. InARITH ’07: Pro- ceedings of the 18th IEEE Symposium on Computer Arithmetic, pages 169–176, Washington, DC, 2007. IEEE Computer Society

    2007

  12. [12]

    Brisebarre and G

    N. Brisebarre and G. Hanrot. Integer points close to a transcendental curve and correctly- rounded evaluation of a function. working paper or preprint, 2023

    2023

  13. [13]

    Brisebarre, G

    N. Brisebarre, G. Hanrot, J.-M. Muller, and P. Zimmermann. Correctly rounded evaluation of a function: Why, how, and at what cost?ACM Comput. Surv., 58(1), Sept. 2025

    2025

  14. [14]

    Brisebarre and M

    N. Brisebarre and M. Joldes. Chebyshev interpolation polynomial-based tools for rigorous computing. In W. Koepf, editor,Symbolic and Algebraic Computation, International Sympo- sium, ISSAC 2010, Munich, Germany, July 25-28, 2010, Proceedings, pages 147–154. ACM, 2010

    2010

  15. [15]

    J. W. S. Cassels.An introduction to the geometry of numbers. Classics in Mathematics. Springer-Verlag, Berlin, 1997. Corrected reprint of the 1971 edition

    1997

  16. [16]

    E. W. Cheney.Introduction to approximation theory. AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition

    1998

  17. [17]

    Chevillard.Évaluation efficace de fonctions numériques – Outils et exemples

    S. Chevillard.Évaluation efficace de fonctions numériques – Outils et exemples. PhD thesis, École normale supérieure de Lyon – Université de Lyon, 2009. In French

    2009

  18. [18]

    Cohen.A course in computational algebraic number theory, volume 138 ofGraduate Texts in Mathematics

    H. Cohen.A course in computational algebraic number theory, volume 138 ofGraduate Texts in Mathematics. Springer-Verlag, Berlin, 1993

    1993

  19. [19]

    Coppersmith

    D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabili- ties.J. Cryptology, 10(4):233–260, 1997

    1997

  20. [20]

    Coppersmith

    D. Coppersmith. Finding small solutions to small degree polynomials. In J. H. Silverman, editor,Proceedings of Cryptography and Lattices (CaLC), volume 2146 ofLecture Notes in Computer Science, pages 20–31. Springer-Verlag, Berlin, 2001

    2001

  21. [21]

    Daramy-Loirat, D

    C. Daramy-Loirat, D. Defour, F. de Dinechin, M. Gallet, N. Gast, C. Q. Lauter, and J.-M. Muller. CR-LIBM, a library of correctly-rounded elementary functions in double- precision. Technical report, LIP Laboratory, Arenaire team, Available athttps://ens-lyon. hal.science/ensl-01529804/file/crlibm.pdf, Dec. 2006

    2006

  22. [22]

    N. D. Elkies. Rational points near curves and small nonzero|𝑥3 −𝑦 2| via lattice reduction. In W. Bosma, editor,Proceedings of the 4th Algorithmic Number Theory Symposium (ANTS IV), volume 1838 ofLecture Notes in Computer Science, pages 33–63. Springer-Verlag, Berlin, 2000

    2000

  23. [23]

    Fox and I

    L. Fox and I. B. Parker.Chebyshev polynomials in numerical analysis. Oxford University Press, London-New York-Toronto, Ont., 1968

    1968

  24. [24]

    F. Gramain. Sur le lemme de Siegel (d’après E. Bombieri et J. Vaaler).Publications mathé- matiques de l’Univ. P. et M. Curie, 64:fascicule 1, 1983-1984

    1983

  25. [25]

    P. M. Gruber and C. G. Lekkerkerker.Geometry of numbers, volume 37 ofNorth-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 2nd edition, 1987

    1987

  26. [26]

    Harvey and J

    D. Harvey and J. van der Hoeven. Integer multiplication in time𝑂(𝑛log𝑛 ).Ann. of Math. (2), 193(2):563–617, 2021

    2021

  27. [27]

    D. R. Heath-Brown. The density of rational points on curves and surfaces.Ann. of Math. (2), 155(2):553–595, 2002

    2002

  28. [28]

    V. Jarník. Über die Gitterpunkte auf konvexen Kurven.Math. Z., 24(1):500–518, 1926

    1926

  29. [29]

    Jiménez Calvo, J

    I. Jiménez Calvo, J. Herranz, and G. Sáez. A new algorithm to search for small nonzero |𝑥3 −𝑦 2|values.Math. Comp., 78(268):2435–2444, 2009

    2009

  30. [30]

    Johansson

    F. Johansson. Arb: efficient arbitrary-precision midpoint-radius interval arithmetic.IEEE Trans. Comput., 66(8):1281–1292, 2017

    2017

  31. [31]

    Khémira.Approximants de Hermite-Padé, déterminants d’interpolation et approximation diophantienne

    S. Khémira.Approximants de Hermite-Padé, déterminants d’interpolation et approximation diophantienne. PhD thesis, Université Paris 6, Paris, France, 2005. INTEGER POINTS CLOSE TO A TRANSCENDENTAL CUR VE 25

    2005

  32. [32]

    Khémira and P

    S. Khémira and P. Voutier. Approximation diophantienne et approximants de Hermite-Padé de type I de fonctions exponentielles.Ann. Sci. Math. Québec, 35(1):85–116, 2011

    2011

  33. [33]

    O. Knill. Cauchy-Binet for pseudo-determinants.Linear Algebra Appl., 459:522–547, 2014

    2014

  34. [34]

    C. Q. Lauter.Arrondi Correct de Fonctions Mathématiques. PhD thesis, École Normale Supérieure de Lyon, Lyon, France, Oct. 2008

    2008

  35. [35]

    Lefèvre.Moyens Arithmétiques Pour un Calcul Fiable

    V. Lefèvre.Moyens Arithmétiques Pour un Calcul Fiable. PhD thesis, École Normale Supérieure de Lyon, Lyon, France, 2000. ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/ RR1999/RR1999-06.ps.Z

    2000

  36. [36]

    V. Lefèvre. New results on the distance between a segment andZ2. Application to the exact rounding. InProceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17), pages 68–75. IEEE Computer Society Press, Los Alamitos, CA, June 2005

    2005

  37. [37]

    Lefèvre and J.-M

    V. Lefèvre and J.-M. Muller. Worst cases for correct rounding of the elementary functions in double precision. In N. Burgess and L. Ciminiera, editors,Proceedings of the 15th IEEE Symposium on Computer Arithmetic (ARITH-16), pages 111–118, Vail, CO, June 2001

    2001

  38. [38]

    A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients.Math. Ann., 261(4):515–534, 1982

    1982

  39. [39]

    Lovász.An algorithmic theory of numbers, graphs and convexity, volume 50 ofCBMS- NSF Regional Conference Series in Applied Mathematics

    L. Lovász.An algorithmic theory of numbers, graphs and convexity, volume 50 ofCBMS- NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1986

    1986

  40. [40]

    J. C. Mason and D. C. Handscomb.Chebyshev polynomials. CRC Press, 2002

    2002

  41. [41]

    Muller, N

    J.-M. Muller, N. Brisebarre, F. de Dinechin, C.-P. Jeannerod, V. Lefèvre, G. Melquiond, N. Revol, D. Stehlé, and S. Torres.Handbook of Floating-Point Arithmetic. Birkhäuser, 2010

    2010

  42. [42]

    Y. V. Nesterenko and M. Waldschmidt. On the approximation of the values of exponential function and logarithm by algebraic numbers (in Russian).Mat. Zapiski, 2:23–42, 1996. Available in English athttps://arxiv.org/abs/math/0002047

    work page internal anchor Pith review Pith/arXiv arXiv 1996

  43. [43]

    P. Q. Nguyen and D. Stehlé. An LLL algorithm with quadratic complexity.SIAM J. Comput., 39(3):874–903, 2009

    2009

  44. [44]

    Springer, 2010

    P.Q.NguyenandB.Vallée, editors.The LLL Algorithm - Survey and Applications.Information Security and Cryptography. Springer, 2010

    2010

  45. [45]

    Plonka, D

    G. Plonka, D. Potts, G. Steidl, and M. Tasche.Numerical Fourier analysis. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, Cham, 2018

    2018

  46. [46]

    M. J. D. Powell.Approximation theory and methods. Cambridge University Press, 1981

    1981

  47. [47]

    T. J. Rivlin.The Chebyshev polynomials. Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics

    1974

  48. [48]

    T. Rivoal. Convergents and irrationality measures of logarithms.Rev. Mat. Iberoam., 23(3):931– 952, 2007

    2007

  49. [49]

    Sibidanov, P

    A. Sibidanov, P. Zimmermann, and S. Glondu. The CORE-MATH project. In29th IEEE Symposium on Computer Arithmetic, ARITH 2022, Lyon, France, September 12-14, 2022, pages 26–34. IEEE, 2022

    2022

  50. [50]

    D. Stehlé. On the randomness of bits generated by sufficiently smooth functions. In F. Hess, S. Pauli, and M. E. Pohst, editors,Proceedings of the 7th Algorithmic Number Theory Symposium, ANTS VII, volume 4076 ofLecture Notes in Computer Science, pages 257–274. Springer-Verlag, Berlin, 2006

    2006

  51. [51]

    Stehlé, V

    D. Stehlé, V. Lefèvre, and P. Zimmermann. Searching Worst Cases of a One-Variable Function Using Lattice Reduction.IEEE Trans. Comput., 54(3):340–346, Mar. 2005

    2005

  52. [52]

    G. Strang. The discrete cosine transform.SIAM Rev., 41(1):135–147, 1999

    1999

  53. [53]

    Torres.Tools for the Design of Reliable and Efficient Functions Evaluation Libraries

    S. Torres.Tools for the Design of Reliable and Efficient Functions Evaluation Libraries. PhD thesis, École normale supérieure de Lyon – Université de Lyon, Lyon, France, 2016

    2016

  54. [54]

    L. N. Trefethen.Approximation Theory and Approximation Practice. SIAM, 2013

    2013

  55. [55]

    Tucker.Validated numerics, A short introduction to rigorous computations

    W. Tucker.Validated numerics, A short introduction to rigorous computations. Princeton University Press, Princeton, NJ, 2011. A short introduction to rigorous computations

    2011

  56. [56]

    von zur Gathen and J

    J. von zur Gathen and J. Gerhard.Modern computer algebra. Cambridge University Press, third edition, 2013

    2013

  57. [57]

    K. Xu. The Chebyshev points of the first kind.Appl. Numer. Math., 102:17–30, 2016

    2016

  58. [58]

    monomials

    A. Zygmund.Trigonometric series. Vol. I, II. Cambridge Mathematical Library. Cambridge University Press, Cambridge, third edition, 2002. AppendixA.Proofs of f acts regarding Chebyshev polynomials First, we recall the aliasing phenomenon in the case of Chebyshev nodes of the first kind. Proposition A.1.For all𝑁⩾1, 26 N. BRISEBARRE AND G. HANROT ∙ for 𝑘 = 0...

    2002