Previous-Copy Compression: Quantitative Barriers

1 Introduction

The base-\(b\) expansion of an algebraic irrational number is expected to have little repetitive structure. A theorem of Adamczewski and Bugeaud shows that its factor complexity cannot be bounded linearly: if \(p(n)\) denotes the number of distinct length-\(n\) blocks in the expansion, then

Their method is based on a Diophantine principle: sufficiently strong repetitions in a base-\(b\) expansion yield rational approximations that are too good for an algebraic irrational number.

In a previous note, this principle was applied to online previous-copy compression. In that model, a finite word \(W\) is parsed from left to right into phrases. Each phrase is either a literal symbol or an exact copy whose source starts earlier in the word; overlap between source and target is allowed. Let \(\oc(W)\) be the minimum number of phrases in such a parsing. The main result was

for every algebraic irrational \(\alpha\). Consequently every standard LZ77-type previous-factor parsing of \(w_N(\alpha)\) has \(\omega(\log N)\) phrases.

The present note packages the repetition obstruction in a finite profile \(\Theta_\alpha(T)\), proves the exact bridge from this profile to previous-copy complexity, and identifies the Diophantine obstruction behind possible quantitative improvements.

The central quantitative issue is the following. A repetition

gives a rational approximation with denominator dividing

or equivalently a small distance to an integer,

The qualitative tube finiteness proved below is a direct consequence of the Subspace Theorem. The point of formulating it separately is that an effective threshold for this tube problem would yield explicit quantitative previous-copy lower bounds.

2 Diophantine inputs

Let

be an infinite word over a finite set of integers. For \(i\leq j\), write

We use the following form of the Adamczewski--Bugeaud repetition criterion.

Theorem 2.1 (Exact repetition criterion).

Let \(b\geq 2\). Suppose that there exist \(\rho>1\) and integer triples

\[ 0\leq r_m<s_m<t_m \]

such that

\[ s_m-r_m\to\infty, \qquad t_m\geq \rho s_m, \]

and

\[ \mathbf a[r_m+1,r_m+t_m-s_m] = \mathbf a[s_m+1,t_m] \]

for every \(m\). Then

\[ \sum_{n\geq 1}a_n b^{-n} \]

is rational or transcendental.

We also use Ridout's theorem in the following form.

Theorem 2.2 (Ridout).

Let \(S\) be a finite set of rational primes, let \(\xi\) be algebraic, and let \(\varepsilon>0\). Then there are only finitely many rational numbers \(P/Q\), written in lowest terms, such that all prime divisors of \(Q\) belong to \(S\) and

\[ \left|\xi-\frac{P}{Q}\right|<Q^{-1-\varepsilon}. \]

Finally, we use the qualitative Subspace Theorem over a number field. We shall apply it with \(K=\mathbb Q(\alpha)\), with one distinguished real place corresponding to the given embedding of \(\alpha\), and with the finite places of \(K\) above the rational primes dividing \(b\).

Theorem 2.3 (Subspace Theorem, qualitative form).

Let \(K\) be a number field, let \(S\) be a finite set of places of \(K\), and for each \(v\in S\) let

\[ L_{v,1},\ldots,L_{v,n} \]

be linearly independent linear forms in \(n\) variables with coefficients in \(K\). For every \(\delta>0\), the solutions \(x\in K^n\setminus\{0\}\) of

\[ \prod_{v\in S}\prod_{i=1}^n |L_{v,i}(x)|_v < H(x)^{-\delta} \]

lie in finitely many proper \(K\)-linear subspaces of \(K^n\).

In our applications, the points \(x\) are rational integer vectors. Hence, after passing to an infinite subsequence inside one of the exceptional \(K\)-subspaces, the rational integer points lie in a proper rational subspace. Equivalently, one may take a non-trivial rational linear relation among them.

We use normalized absolute values. If \(q\in\mathbb Q^\times\), then for a rational prime \(p\),

In particular, for the finite places above primes dividing \(b\), the contribution of \(b^r\) is \(b^{-r}\), and the contribution of \(b^{r+d}\) is \(b^{-(r+d)}\).

3 The finite stammering profile

Definition 3.1.

Let \(\mathbf a=a_1a_2\cdots\) be an infinite word. For \(T\geq 1\), define

\[ \Theta_{\mathbf a}(T) = \sup\left\{ \frac{t}{s}-1: 0\leq r<s<t,\quad t\geq T, \mathbf a[r+1,r+t-s]=\mathbf a[s+1,t] \right\}. \]

If the set is empty, we put \(\Theta_{\mathbf a}(T)=0\).

If \(\mathbf a\) is the base-\(b\) digit sequence of \(\alpha\), write \(\Theta_\alpha(T)\).

The quantity \(\Theta_{\mathbf a}(T)\) measures the strongest exact repetition, in the Adamczewski--Bugeaud sense, whose endpoint is at least \(T\).

Theorem 3.2 (Qualitative decay).

Let \(b\geq 2\), and let

\[ \alpha=\sum_{n\geq 1}a_n b^{-n} \in (0,1)\cap(\overline{\mathbb Q}\setminus\mathbb Q). \]

Then

\[ \Theta_\alpha(T)\to 0. \]

4 Online previous-copy parsing and the profile bridge

Let \(W=W[1]\cdots W[N]\) be a finite word.

Definition 4.1.

An online previous-copy parsing of \(W\) is a factorization

\[ W=F_1\cdots F_z \]

with boundaries

\[ 0=n_0<n_1<\cdots<n_z=N \]

such that each phrase

\[ F_j=W[n_{j-1}+1,n_j] \]

is either:

1. a literal, in which case \(|F_j|=1\), or

2. a copy: writing \(s=n_{j-1}\), \(t=n_j\), \(L=t-s\), there exists \(p\leq s\) such that

   \[ W[p+h]=W[s+1+h] \qquad(0\leq h<L). \]

The source may overlap the target. Let \(\oc(W)\) be the minimum possible number of phrases.

Theorem 4.2 (Profile-to-compression bridge).

Let \(\mathbf a=a_1a_2\cdots\) be an infinite word and let

\[ W_N=a_1\cdots a_N. \]

For \(T\geq 2\), define

\[ \eta_{\mathbf a}(T) = \max\left\{\Theta_{\mathbf a}(T),\frac{1}{T-1}\right\}. \]

Then, for every \(N>T\),

\[ \oc(W_N) \geq \frac{\log(N/T)}{\log(1+\eta_{\mathbf a}(T))}. \]

Corollary 4.3.

Let \(b\geq 2\) and let

\[ \alpha\in(0,1)\cap(\overline{\mathbb Q}\setminus\mathbb Q). \]

Then

\[ \oc(w_N(\alpha))=\omega(\log N). \]

5 Strong repetitions and rational approximants

Let

be an exact repetition, with

Thus

The repetition says

Let \(\beta\) be the rational number whose base-\(b\) expansion agrees with \(\alpha\) through position \(r\), and thereafter is periodic with period

Then \(\beta\) has denominator dividing

and \(\alpha\) and \(\beta\) agree through at least position

Hence, for some integer \(P\),

and

Equivalently,

Thus

We call the repetition \(\varepsilon\)-strong if

6 A subcritical barrier

The following result eliminates repetitions in which the two copies overlap too much relative to the repeated length.

Theorem 6.1 (Subcritical barrier).

Let \(b\geq 2\), and let

\[ \alpha\in(0,1)\cap(\overline{\mathbb Q}\setminus\mathbb Q). \]

Fix \(\varepsilon>0\) and \(0<\lambda<1\). Then there are only finitely many exact repetitions

\[ \mathbf a[r+1,r+L]=\mathbf a[r+d+1,r+d+L] \]

such that

\[ L\geq \varepsilon(r+d) \]

and

\[ d\leq(1-\lambda)L. \]

7 The linear-height exponential tube problem

The subcritical theorem leaves the regime

Together with

this gives

Hence

Moreover

Since \(L\geq\varepsilon d\), for all sufficiently large \(d\) this implies

This motivates the following auxiliary problem.

Definition 7.1.

For \(C>0\) and \(0<\theta<1\), let \(D_{\alpha,b}(C,\theta)\) be the least integer \(D\), if it exists, such that there are no solutions

\[ r,d\geq1, \qquad r\leq Cd, \qquad d\geq D, \]

to

\[ \normZ{\alpha b^r(b^d-1)}<\theta^d. \]

The next theorem proves that \(D_{\alpha,b}(C,\theta)\) is finite. No effective upper bound is obtained.

Theorem 7.2 (Qualitative tube finiteness).

Let \(b\geq 2\), let

\[ \alpha\in\overline{\mathbb Q}\setminus\mathbb Q \]

be real, let \(C>0\), and let \(0<\theta<1\). Then there are only finitely many pairs

\[ r,d\geq1, \qquad r\leq Cd, \]

such that

\[ \normZ{\alpha b^r(b^d-1)}<\theta^d. \]

Corollary 7.3 (Critical repetitions are finite).

Fix \(\varepsilon>0\) and \(0<\lambda<1\). There are only finitely many exact repetitions satisfying

\[ L\geq\varepsilon(r+d) \]

and

\[ d>(1-\lambda)L. \]

8 Conditional quantitative consequences

The preceding finiteness results are qualitative. We now record exactly what kind of effective input would imply explicit lower bounds for online previous-copy complexity.

For \(\varepsilon>0\), let \(R_{\alpha,b}(\varepsilon)\) be any threshold such that there are no repetitions

with endpoint

and

The qualitative results above imply that \(R_{\alpha,b}(\varepsilon)<\infty\) for each fixed \(\varepsilon>0\), but they do not provide an effective bound.

Lemma 8.1.

If

\[ R_{\alpha,b}(\varepsilon)\leq F(\varepsilon) \]

for all sufficiently small \(\varepsilon\), then

\[ \Theta_\alpha(T)\leq \varepsilon \qquad (T\geq F(\varepsilon)). \]

Theorem 8.2 (Exponential threshold implies power-logarithmic compression).

Assume that there exist constants \(K,A>0\) such that, for all sufficiently small \(\varepsilon>0\),

\[ R_{\alpha,b}(\varepsilon) \leq \exp(K\varepsilon^{-A}). \]

Then

\[ \oc(w_N(\alpha)) \gg_{\alpha,b} (\log N)^{1+1/A}. \]

Theorem 8.3 (Double-exponential threshold).

Assume that, for some \(K,A>0\),

\[ R_{\alpha,b}(\varepsilon) \leq \exp\exp(K\varepsilon^{-A}) \]

for all sufficiently small \(\varepsilon>0\). Then

\[ \oc(w_N(\alpha)) \gg_{\alpha,b} \log N(\log\log N)^{1/A}. \]

Remark 8.4.

The exponential or double-exponential hypotheses above are not proved in this note. They would require effective forms of the Diophantine finiteness results used in the subcritical and tube arguments. The qualitative Subspace Theorem does not provide such thresholds.

9 The effective tube problem

The critical part of the threshold \(R_{\alpha,b}(\varepsilon)\) is governed by the linear-height exponential tube problem.

Problem 9.1 (Effective linear-height exponential tube problem).

Let

\[ \alpha\in\overline{\mathbb Q}\setminus\mathbb Q, \qquad b\geq 2. \]

Find an explicit upper bound for

\[ D_{\alpha,b}(C,\theta), \]

where \(D_{\alpha,b}(C,\theta)\) is the least integer \(D\) such that there are no solutions

\[ r,d\geq1,\qquad r\leq Cd,\qquad d\geq D \]

to

\[ \normZ{\alpha b^r(b^d-1)}<\theta^d. \]

In the compression application one has

Thus a bound of the form

would imply an exponential threshold for \(R_{\alpha,b}(\varepsilon)\), up to the corresponding effective subcritical estimate. A double-exponential bound would imply the double-exponential threshold.

10 A partial effective range

Liouville's inequality gives an effective bound only in a range much stronger than the one needed for compression.

Proposition 10.1 (Liouville range).

Let \(D=\deg(\alpha)\). If

\[ \theta<b^{-(D-1)(C+1)}, \]

then \(D_{\alpha,b}(C,\theta)\) is effectively bounded in terms of \(\alpha,b,C,\theta\).

Remark 10.2.

In the compression regime,

\[ C\asymp\varepsilon^{-1}, \qquad \theta=b^{-c\varepsilon}. \]

For small \(\varepsilon\), the Liouville condition is far stronger than what is available. Thus Roth--Ridout--Subspace type input is genuinely needed.

11 Scope

The results in this note are qualitative except for the elementary Liouville range and the conditional implications in Section 8. In particular, we do not prove

or

Such bounds would follow from effective estimates for the repetition threshold \(R_{\alpha,b}(\varepsilon)\), or more specifically from effective bounds for the linear-height exponential tube problem.

The main unconditional conclusions are:

the subcritical finiteness theorem, and the qualitative finiteness of the tube problem.

Declaration of generative AI and AI-assisted technologies in the writing process

During the preparation of this work, ChatGPT, by OpenAI, was used to assist with mathematical drafting, formalization, review, and editing. This work is shared as a preliminary AI-assisted mathematical note. The mathematical content may have been only partially reviewed and may contain errors; it should not be treated as peer-reviewed or as a fully verified manuscript.