On Ruzsa's conjecture on congruence preserving functions

This paper proves that Ruzsa's conjecture on congruence-preserving sequences holds true if the associated generating function has at most two singular directions at the origin, thereby showing that any potential counterexample must exhibit at least three such directions.

The Gist

Imagine you have a long line of numbers, like a secret code: $a_0, a_1, a_2, a_3, \dots$.

In the world of math, there's a special rule for these numbers called "congruence preserving." It sounds fancy, but it's actually a simple pattern: if you take any number in the line and add a step size $k$ to its position, the new number must leave the same "remainder" when divided by $k$ as the old one did.

Think of it like a clock. If you know the time is 3 o'clock, and you add 12 hours, it's still 3 o'clock. The rule says our sequence behaves like a clock for every possible step size.

The Big Question: Is it a Simple Formula?

Mathematicians have known for a long time that if you plug $n$ into a simple polynomial (like $n^2 + 3n + 5$), the resulting numbers will always follow this "clock rule."

But here is the mystery: Is the reverse true?
If a sequence follows the clock rule and doesn't grow too fast, does it have to be a simple polynomial?

This is Ruzsa's Conjecture. It's like asking: "If a mystery shape fits perfectly inside a square frame and isn't too huge, does it have to be a square?"

For decades, mathematicians proved this is true if the numbers grow very slowly. But if they grow a bit faster (but still under a specific limit called $e$, roughly 2.718), the answer remained a mystery. Could there be a weird, non-polynomial sequence that tricks the rule?

The New Discovery: The "Singular Direction" Test

The author of this paper, É. Delaygue, didn't solve the whole mystery, but he found a very clever way to narrow it down. He proved that if the sequence follows the clock rule, grows slowly enough, and has a specific geometric property regarding its "directions," then it must be a simple polynomial.

Here is the analogy for the technical part:

Imagine the sequence of numbers is a radio signal.

1. The Signal: The sequence generates a "wave" (a mathematical function).
2. The Noise (Singularities): Sometimes, this wave hits a wall and stops working. These walls are called "singularities."
3. The Direction: From the center of the room (where the signal starts), these walls point in specific directions.

The paper proves a new rule: If the signal only hits walls in at most two directions, it cannot be a weird, complex shape. It must be a simple polynomial.

If a "fake" sequence (a counterexample) exists, it would have to be so chaotic that it hits walls in three or more directions.

How Did They Prove It? (The Detective Work)

The author used a mix of two different detective tools to catch the "fake" sequences:

1. The Size Check (The "Too Big" Trap)
Mathematicians use a special grid of numbers called Hankel determinants to check the complexity of a sequence.

• Think of these determinants as a "complexity score."
• If the sequence is a simple polynomial, the score eventually becomes zero.
• The author used a geometric trick (involving "transfinite diameter," which is like measuring the size of a star-shaped cloud) to prove that if the sequence is too simple (only 2 directions), the complexity score must get tiny.

2. The Divisibility Check (The "Too Small" Trap)
Because the sequence follows the "clock rule" (congruences), the author proved that these complexity scores must be divisible by huge prime numbers.

• Imagine the score is a number that must be divisible by 2, then 3, then 5, then 7... all the way up.
• This forces the score to be a massive number (or zero).

The Showdown:
The author put these two traps together:

• Trap 1 says: "The score must be incredibly small (almost zero)."
• Trap 2 says: "The score must be incredibly huge (divisible by many primes)."

The only number that is both "incredibly small" and "incredibly huge" is Zero.

So, the complexity score hits zero. When the score hits zero, the sequence is mathematically proven to be a simple polynomial.

The Bottom Line

This paper doesn't solve the whole Ruzsa Conjecture yet. It's like finding a new rule for a maze: "If the maze only has two dead ends, you can't get lost."

The result tells us: If a counterexample to Ruzsa's conjecture exists, it must be a very complex, multi-directional monster with at least three "singular directions." If it's simpler than that, it's definitely just a polynomial in disguise.

This brings us one step closer to understanding the fundamental nature of these number sequences, using a blend of geometry, number theory, and a bit of detective logic.

Technical Summary

Here is a detailed technical summary of the paper "On Ruzsa's Conjecture on Congruence Preserving Functions" by É. Delaygue.

1. Problem Statement and Context

The Core Conjecture:
The paper addresses Ruzsa's Conjecture, which concerns sequences of integers $(a_n)_{n \ge 0}$ that preserve congruences. A sequence is called a pseudo-polynomial if it satisfies:
$$a_{n+k} \equiv a_n \pmod k \quad \text{for all } n, k \in \mathbb{N}.$$
While any polynomial sequence $(P(n))_{n \ge 0}$ with $P \in \mathbb{Z}[x]$ is a pseudo-polynomial, the converse is not immediately obvious. Ruzsa conjectured that a growth condition forces pseudo-polynomials to be actual polynomial sequences.

Conjecture A (Ruzsa):
If a pseudo-polynomial $(a_n)$ satisfies the growth condition:
$$\limsup_{n \to +\infty} |a_n|^{1/n} < e,$$
then $(a_n)$ must be a polynomial sequence.

Previous State of the Art:

• Sharpness: Hall (1971) constructed a counterexample where the limit is exactly $e$, showing the bound is sharp.
• Partial Proofs: The conjecture was proven for stricter bounds:
  • $e-1$ by Hall and Ruzsa (1971).
  • $e^{0.66}$ by Perelli and Zannier (1984).
  • $e^{0.75}$ by Zannier (1996).
• General Case: The case where the limit is strictly less than $e$ but greater than $e^{0.75}$ remained open.

Refined Setting:
The paper works with primary pseudo-polynomials, where the congruence condition is restricted to prime moduli ($a_{n+p} \equiv a_n \pmod p$ for all primes $p$). Perelli and Zannier previously proved that such sequences are P-recursive (their generating series $f(x) = \sum a_n x^n$ is D-finite) under the growth condition $< e$.

2. Methodology

The author's approach adapts Carlson's method, originally used for the Pólya–Carlson dichotomy, combined with a refined analysis of Hankel determinants. The strategy involves proving that the generating series $f(x)$ is a rational function, which implies the sequence is polynomial.

The proof proceeds in three main technical steps:

A. Establishing an Archimedean Upper Bound

The author utilizes Kronecker's Rationality Criterion (Theorem B), which states that a power series is rational if and only if almost all its Hankel determinants vanish.

• Hankel Determinant: $H_n(f) = \det(a_{i+j})_{0 \le i,j \le n-1}$.
• Tool: Pólya's Inequality relates the growth of Hankel determinants to the transfinite diameter of the set of singularities.
• Geometric Argument: Since $f$ is D-finite with radius of convergence $\rho > 1/e$ and has at most $r$ singular directions, the singularities form a "hedgehog" set $K$.
• Dubinin's Theorem: The author applies a theorem by Dubinin to estimate the transfinite diameter of this hedgehog. For $r$ singular directions, the transfinite diameter is bounded by $(\max |a_i|^{r/4})^{1/r}$.
• Result: If $f$ has at most two singular directions ($r \le 2$), the author derives:
  $$\limsup_{n \to \infty} |\det H_n(f)|^{1/n^2} \le \frac{1}{4^{1/r}\rho} < \frac{e}{2}.$$

B. Establishing a Non-Archimedean Lower Bound

The author exploits the arithmetic properties of primary pseudo-polynomials.

• Binomial Transform: The sequence is transformed via the binomial transform $(b_n)$. It is known that $\det H_n(f) = \det H_n(g)$, where $g$ is the generating series of $(b_n)$.
• Divisibility: Using a result from Perelli and Zannier, the terms $b_n$ are divisible by the product of all primes $\le n$.
• Result: This implies that $\det H_n(f)$ is divisible by a large integer product:
  $$\prod_{p \le n-1} p^{n-p}.$$
• Asymptotic Analysis: Using the Prime Number Theorem and Chebyshev functions, the logarithm of this divisor grows as:
  $$\log \left( \prod_{p \le n-1} p^{n-p} \right) \sim \frac{n^2}{2}.$$
  Thus, the magnitude of the determinant (if non-zero) must grow at least as $e^{n^2/2}$.

C. The Contradiction

The proof concludes by comparing the two bounds:

1. Upper Bound (Archimedean): Growth rate $\approx (e/2)^{n^2}$.
2. Lower Bound (Non-Archimedean): Growth rate $\approx e^{n^2/2} = (\sqrt{e})^{n^2}$.

Since $\sqrt{e} \approx 1.648$ and $e/2 \approx 1.359$, we have $\sqrt{e} > e/2$.
For sufficiently large $n$, the non-zero lower bound exceeds the upper bound. This contradiction forces $\det H_n(f) = 0$ for all large $n$.

3. Key Contributions and Results

Main Theorem (Theorem 1.1):
Let $(a_n)_{n \ge 0}$ be a primary pseudo-polynomial such that $\limsup |a_n|^{1/n} < e$. If its generating series $f$ has at most two singular directions at $x=0$, then $(a_n)$ is a polynomial sequence.

Key Technical Innovations:

1. Application of Dubinin's Theorem: The paper successfully adapts Dubinin's result on the transfinite diameter of hedgehogs to the context of D-finite functions with limited singular directions.
2. Synthesis of Methods: It bridges the gap between analytic number theory (Carlson's method, Pólya's inequality) and arithmetic combinatorics (Hankel determinant divisibility).
3. Refinement of Singularity Constraints: The paper moves beyond the general D-finite case (where the number of singularities is unbounded and large) to a specific geometric constraint (number of singular directions $\le 2$).

4. Significance and Implications

• Progress on Ruzsa's Conjecture: This is the first new case of Ruzsa's conjecture proven since Zannier's 1996 result. It confirms the conjecture for a specific, non-trivial class of sequences defined by their singularity structure.
• Characterization of Counterexamples: The result implies that if a counterexample to Ruzsa's conjecture exists (a non-polynomial pseudo-polynomial with growth $< e$), it must have at least three singular directions at the origin. This narrows the search space for potential counterexamples significantly.
• Methodological Impact: The paper demonstrates the power of combining Pólya–Carlson dichotomy techniques with non-Archimedean divisibility arguments. This approach, previously used by Dimitrov for the Schinzel–Zassenhaus conjecture, is shown to be effective for problems involving congruence-preserving functions.
• Effective Bounds: While Perelli and Zannier proved that such sequences are D-finite, their bounds on the number of singularities were too large to apply the "two singular directions" condition directly. This paper provides a conditional proof that bypasses the need for explicit bounds on the order of the differential operator by imposing a geometric constraint on the singularities.

In summary, Delaygue's paper establishes that the "geometry" of the generating function's singularities (specifically, having $\le 2$ directions) is sufficient to force a congruence-preserving sequence with sub-exponential growth to be a polynomial, thereby ruling out a broad class of potential counterexamples to Ruzsa's conjecture.