Effective Roth Theorem

Effective Roth Theorem

Definitions and mathematical statement

Encode a real algebraic irrational $\alpha$ by its integer minimal polynomial and a rational interval containing exactly the chosen real root. Given also rational $\varepsilon>0$, the requested single total algorithm must output an integer $Q\ge1$ such that \[ \gcd(p,q)=1,\quad q\ge1,\quad |\alpha-p/q|<q^{-2-\varepsilon}\quad\Longrightarrow\quad q\le Q. \] The algorithm must halt on every valid input; $p$ may be any integer. The bound can be enormous and the running time unrestricted. Merely proving that finitely many such approximations exist, or giving a bound depending on an unspecified noncomputable constant, does not supply this effective version.

Formulation and concept references: [S1].

Short English statement

Can an algorithm compute a guaranteed denominator cutoff for every exceptionally accurate rational approximation to a specified algebraic irrational?

Research attempt

Current frontier.

The issue is a computable location of the last exceptional denominator, not finiteness of the exceptional set. Dill's introduction distinguishes the effective Liouville exponent and special effective improvements from Roth's ineffective exponent $2+\varepsilon$.[S1] Adiceam--Shirandami give effective proportions of algebraic inputs with approximations in specified ranges; their order of limits and height regime do not give a cutoff for each fixed input.[E1] The argument below does not use such a density statement as a pointwise theorem.

Attack route.

There are three natural places to seek a stopping certificate: a polynomial lower bound, the continued-fraction tail, and exhaustion of a quantitatively finite exceptional set. The first works beyond the Liouville threshold. The second isolates a specific infinite-tail estimate. The third is tested against a computability construction in which a single late exceptional convergent encodes a halting time. This last test deliberately changes the representation of the input; it identifies information a successful proof must use, rather than disproving the stated problem.

Attempt.

1. An elementary, fully effective region. Write the supplied irreducible polynomial as $P(X)=\sum_{j=0}^{d}a_jX^j$, with $d\ge2$. From the isolating interval choose an integer $R>|\alpha|+1$ and compute \[ L=\sum_{j=1}^{d}j|a_j|R^{j-1}>0. \] For a candidate satisfying the target inequality, $|\alpha-p/q|<1$, so both $\alpha$ and $p/q$ lie in $(-R,R)$. Irreducibility implies $P(p/q)\ne0$, while $q^dP(p/q)$ is an integer. The mean-value theorem gives \begin{equation}\label{wsref-0-33-30-30-30-36-37-39-30-3a-6c-69-6f-75-76-69-6c-6c-65} q^{-d}\le |P(p/q)|\le L|\alpha-p/q|, \qquad |\alpha-p/q|\ge L^{-1}q^{-d}. \end{equation} Consequently, if $\delta=2+\varepsilon-d>0$, an exception must satisfy $q^\delta<L$. An integer $Q\ge1$ with $Q^\delta\ge L$ can be found by integer search and exact comparison of rational powers. It is a valid cutoff. In particular, this supplies a total algorithm for every quadratic input and every positive rational $\varepsilon$; no continued-fraction period has to be computed. For $d\ge3$ and $0<\varepsilon\le d-2$, the displayed inequality has the wrong exponent and gives no bound on $q$.

2. A precise tail certificate. Let $p_n/q_n$ be the regular continued-fraction convergents of $\alpha$. For sufficiently large $n$, their positive denominators strictly increase. The determinant relation for adjacent convergents and the complete quotient formula give \begin{equation}\label{wsref-0-33-30-30-30-36-37-39-30-3a-63-66} \frac{1}{q_n(q_{n+1}+q_n)} <\left|\alpha-\frac{p_n}{q_n}\right| <\frac{1}{q_nq_{n+1}}. \end{equation} Indeed, writing the next complete quotient as $a_{n+1}+\theta$, with $0<\theta<1$, the exact denominator of the error is $q_n(q_{n+1}+\theta q_n)$. If one could compute $n_0$ for which \begin{equation}\label{wsref-0-33-30-30-30-36-37-39-30-3a-74-61-69-6c} q_{n+1}+q_n\le q_n^{1+\varepsilon}\qquad(n\ge n_0), \end{equation} then no such convergent would be exceptional. A reduced rational with $q>2^{1/\varepsilon}$ and error $<q^{-2-\varepsilon}$ has error $<1/(2q^2)$ and hence is a convergent, by the elementary continued-fraction best-approximation criterion. Thus a bound covering $2^{1/\varepsilon}$ and the finitely many earlier convergent denominators would solve the input instance.

The problem is not that the tail inequality is false. Apply Roth with $\varepsilon/2$ and use the upper bound in (30006790:cf): eventually $q_{n+1}<q_n^{1+\varepsilon/2}$, which implies (30006790:tail) once $q_n^{\varepsilon/2}$ is sufficiently large. This argument proves existence of a tail but supplies no computable starting index. Importing this index from Roth would be exactly the effectivity gap.[S1]

3. Exact enumeration and the gap principle do not certify a tail. For each $q$, only finitely many integers $p$ with $|p|<Rq$ need examination. The comparison of the algebraic number $|\alpha-p/q|$ with the positive algebraic number $q^{-2-\varepsilon}$ is decidable, including equality. Enumeration therefore gives a computable nondecreasing sequence of provisional maxima. Roth implies that this sequence eventually stabilizes, but stabilization is not an observable event in a finite prefix.

For two distinct exceptional reduced fractions with $q'\ge q$, \[ \frac1{qq'}\le\left|\frac pq-\frac{p'}{q'}\right| <q^{-2-\varepsilon}+(q')^{-2-\varepsilon}\le2q^{-2-\varepsilon}, \qquad q'>\tfrac12q^{1+\varepsilon}. \] This is a lower separation bound. It permits an arbitrarily late next exception; it is not an upper bound on the last one. Even a computable upper bound on the number of exceptions does not say when enumeration has finished if the actual number is smaller.

4. A representation-sensitive impossibility lemma. Consider a different input format: a program producing arbitrarily accurate rational approximations to a real number, promised to be quadratic irrational. There is no total computable cutoff procedure on all such programs even for the fixed exponent $\varepsilon=1$.

Here is a direct proof. Given a machine index $e$, construct a continued fraction $\alpha_e=[0;a_1,a_2,\ldots]$ as follows. All digits are $1$ unless the machine first halts at step $t\ge0$. In that event put $n=t+3$, change just the digit $a_{n+1}$ to $q_n^2+1$, and leave every other digit equal to $1$. The denominator $q_n$ before this exceptional digit is the denominator of $[0;1,\ldots,1]$, hence a known increasing Fibonacci number with $q_n\ge3$.

Every finite digit prefix is computable by a finite simulation. Moreover, continued-fraction cylinders of length $j$ have diameter at most the reciprocal square of their least possible denominator, which grows at least as a Fibonacci number. This gives a uniform computable Cauchy name for $\alpha_e$, with no decision about eventual halting. Every $\alpha_e$ is quadratic irrational: its tail is all ones, whose complete quotient $\tau$ satisfies $\tau^2-\tau-1=0$, and a finite continued-fraction prefix acts on $\tau$ by a rational fractional-linear transformation of determinant $\pm1$.

If the machine halts, the exceptional convergent satisfies \[ q_{n+1}=(q_n^2+1)q_n+q_{n-1}>q_n^3, \qquad \left|\alpha_e-\frac{p_n}{q_n}\right|<q_n^{-4}<q_n^{-3}. \] Suppose a cutoff algorithm on the Cauchy-program representation returned $Q_e$. Choose a computable $B$ such that the all-ones denominator $q_{B+3}>Q_e$, and simulate the machine for $B$ steps. If it has not halted, it can never halt later: halting at $t>B$ would create the above exception with denominator exceeding $Q_e$. This decides the halting problem, a contradiction.

The elementary undecidability used here follows by diagonalization: a hypothetical procedure deciding whether a program halts on its own index would allow a program which halts precisely when that procedure predicts that it does not. No unproved Diophantine conjecture enters this lemma.

Stress test.

The representation lemma is not a counterexample to Effective Roth. The original input includes a minimal polynomial and a root-isolating interval, whereas the constructed family supplies only a Cauchy program. There is no uniform method to extract that polynomial and interval from these programs: composing one with the quadratic algorithm in part 1 would give the impossible procedure in part 4. Once a particular machine has halted, its finite exceptional prefix does determine such a polynomial; knowing that this has happened is exactly the unavailable information.

No asymptotic assertion was used to terminate a search. The rational-power comparisons in part 1 and finite algebraic comparisons in part 3 are exact. The strict inequality in the problem is respected at the cutoff and at possible equality cases. The continued-fraction argument works after subtracting an integer as well, so negative $\alpha$ and arbitrary integer numerators are not excluded. The algorithmic impossibility argument is an obstruction to discarding the input's algebraic certificate, not evidence that the correctly encoded target is false.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The notebook proves the effective region $\varepsilon>d-2$, identifies the missing computable continued-fraction tail, and proves a representation barrier against replacing the minimal-polynomial input by unrestricted numerical access. These are not claimed as new frontier results. For degree at least three in the remaining exponent range, the missing step is a way to use the supplied algebraic certificate to bound the last large partial quotient without importing an ineffective Roth constant. No such step is established.

Sources

• S1 Effective Approximation and Diophantine Applications; arXiv1601.02243v1,10January2016. https://arxiv.org/pdf/1601.02243v1. Catalogue formulation source.
• E1 Faustin Adiceam and Victor Shirandami, Probabilistic Effectivity in the Subspace Theorem, arXiv:2411.01247v2 (13 November 2024), Sections 1.1--1.2, Theorem 1.3 and the order of limits in $1.9$. Research in Number Theory 12, article 8 $2026$, DOI 10.1007/s40993-025-00692-0. https://arxiv.org/abs/2411.01247. Consulted 27 September 2026. Used for the probabilistic/pointwise distinction, not as a pointwise effective Roth theorem.