arXiv:2606.04858v1

Integer points close to a transcendental curve: an algorithmic approach

Nicolas Brisebarre, Guillaume Hanrot

math.NTcs.SC11Y9941A0565G5011D7511J25

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.

AI-generated audit

Audit summary

Audited against arXiv v1

Not a correctness certificate. A “Correct” result may include yellow typos or minor formal corrections that do not affect substantive soundness. It means this audit found no unresolved substantive error under the stated criteria; it does not replace expert scrutiny or formal verification.

Current report

Detailed mathematical audit

Generated August 18, 2026
01Statements3 reported findingsCorrect

The deterministic correctness and complexity claims for the two lattice-based algorithms are supported. The asymptotic success and call-count estimates are explicitly labelled heuristic and are not presented as unconditional theorems.

Theorem 4.3 and Corollary 4.10Correct

Correctness of the lattice-generated algebraic certificates

Pages 11–16 · Section 4.3 and Corollary 4.10 · arXiv:2606.04858v1

The Chebyshev interpolation bounds convert small sampled lattice vectors into two integer polynomials uniformly small on the entire weighted strip. The determinant and norm hypotheses guarantee their linear independence. Every admissible integer point therefore makes both polynomials vanish, so the resultant step cannot discard a solution. Corollary 4.10 verifies that LLL supplies vectors within the size threshold under its explicit determinant condition.

Propositions 4.11–4.12Correct

Complexity of the lattice-building and reduction stages

Pages 16–17 · Section 4.4.1 · arXiv:2606.04858v1

The bit sizes of sampled values and lattice entries are bounded in terms of the declared evaluation and precision model. Proposition 4.11 accounts for the function evaluations, arithmetic, and discrete cosine transforms in Algorithm 1; Proposition 4.12 then adds the stated lattice-reduction cost for Steps 1–6 of Algorithm 2. The paper expressly limits this deterministic complexity calculation to the two auxiliary-polynomial stage.

Theorems 4.14–4.15Correct

Heuristic performance bounds are correctly scoped

Pages 17–19 · arXiv:2606.04858v1

The faster call counts depend on the stated assumption that the two auxiliary polynomials are coprime; if they are not, Algorithm 2 returns FAIL. The paper repeatedly marks this dependence, and any non-FAIL output remains unconditionally valid. The optimization in γ\gamma, λ\lambda, and the polynomial degree is algebraically consistent with those conditional estimates.

02Proofs2 reported findingsCorrect

The interpolation, lattice-reduction, certificate, and complexity arguments are correct and complete within the declared computational model. Conditional heuristic analyses are kept separate from correctness.

Sections 3–5 and Appendices A–ECorrect and complete

Analytic-to-arithmetic proof chain

Pages 8–34 and appendices · arXiv:2606.04858v1

The bivariate Chebyshev error estimates are applied on ellipses contained in the assumed analytic domains, the weighted monomial enumeration matches the lattice dimension, and the LLL bound is translated to the coefficient norm without reversing an inequality. When the two output polynomials are coprime, the resultant step isolates their common zeros; otherwise the algorithm reports FAIL rather than asserting completeness. The precision analysis includes the guard bits needed for the certified evaluations.

Appendices C and ECorrect and complete

Rigorous interpolation volume and precision bounds

Pages 34–36 and 38–39 · arXiv:2606.04858v1

The determinant estimate is applied to the rigorous coefficient matrix rather than to idealized exact samples, and the rounding remainder is incorporated before invoking the lattice bound. Appendix E propagates the required evaluation precision through the discrete cosine transforms and matrix scaling, giving the bit-size parameter used in Propositions 4.11–4.12. Thus the stated core complexity is tied to an explicit certified-precision model.

03Novelty0 reported findingsNo non-novelty findings

No non-novelty findings.

Detailed audit reportFull reasoning, manuscript locations, and references.
Open report PDF ↗

Author response

Challenge an audit finding

Local workflow preview

A listed author may submit formal evidence that an audit is inaccurate. The response would be considered in a fresh AI re-evaluation; it would not edit the audit automatically.

Paper
arXiv:2606.04858v1
Authors listed
Nicolas Brisebarre, Guillaume Hanrot
Audit date
August 18, 2026
  1. 01Establish identityMatch an authenticated scholarly identity to this paper.
  2. 02Submit evidenceIdentify the finding and give a formal mathematical response.
  3. 03Re-evaluateA separate agent checks the response and records a disposition.
Recommended production method

Authenticate with ORCID, then require an exact arXiv match

MathAudit should accept the identity only when ORCID OAuth authenticates the claimant's iD and this exact arXiv paper appears in arXiv's public authority feed for that iD. A matching name alone is not sufficient.

ORCID OAuth and arXiv authority-record lookup are not connected in this local prototype.

Email fallback for papers without a linked ORCID

A production fallback could send a one-time link only when the submitted address matches an independently maintained author-contact allowlist for this paper. MathAudit must return the same message for every address so the form cannot reveal which contacts are on that list.

This demonstration does not send, store, or compare the address.

Structured response preview

This form remains unavailable until production identity verification succeeds. Nothing entered here is submitted.

This panel never establishes authorship in the local prototype. A production result should be described narrowly as an authenticated ORCID match or control of a separately allowlisted author-contact mailbox.