Proof of 100 Euro Conjecture

This paper confirms the nearly 30-year-old 100 Euro Conjecture by proving that for every real matrix $A$ satisfying $|A|e = ne$, there exists a nonzero vector $x$ such that $|Ax| \ge |x|$ entrywise, utilizing a finite-dimensional reformulation of Ball's plank theorem.

The Gist

Imagine you are a game designer trying to build a maze. You have a set of rules (a matrix) that tells you how to move through the maze. For decades, mathematicians have been stuck on a specific puzzle about these mazes, known as the "100 Euro Conjecture."

Here is the simple story of what this paper does, using everyday analogies.

The Big Puzzle: The "100 Euro" Challenge

Imagine you have a grid of numbers (a matrix). The rule for this specific puzzle is: The sum of the absolute values of the numbers in every single row must equal a specific target number (let's call it $n$).

Think of each row as a team of workers. The rule says: "The total strength of every team must be exactly $n$."

The Question: If you set up the maze this way, is it possible to find a specific path (a vector $x$) through the maze such that, when you apply the maze's rules to your path, the result is at least as big as your original path?

In math terms: Does there exist a path where the output is "bigger" than the input?

• The old answer: For nearly 30 years, the best mathematicians could say was, "Maybe, but we can only guarantee the output is about 30% as big as the input."
• The new answer (This paper): YES! We can guarantee the output is at least 100% as big as the input. In fact, the output is bigger than the input in every single direction.

The Secret Weapon: "Plank Theorem"

How did the author, Teng Zhang, solve this? He didn't just brute-force the math. He used a clever geometric trick called Ball's Plank Theorem.

The Analogy of the Plank:
Imagine you have a giant, solid block of cheese (the "unit ball"). You want to cut through it with a series of thin wooden planks (these represent the rows of your matrix).

• The "Plank Theorem" says: If the total width of all your planks adds up to a certain amount, you cannot cut the cheese into pieces so small that no piece remains whole. There will always be at least one chunk of cheese that sticks out from every plank.

Zhang realized that the "100 Euro Conjecture" is just a specific version of this cheese-cutting problem.

• The "rows" of the matrix are the planks.
• The condition that "row sums equal $n$" means the planks are thick enough.
• The "vector $x$" is the chunk of cheese that sticks out.

By proving that the planks are thick enough, he proved that a "chunk" (a solution vector) must exist that sticks out on all sides.

The "Escape" Metaphor

The paper uses a concept called "Escape."
Imagine you are trapped inside a box (the unit cube or sphere). The matrix $A$ is a set of walls pushing against you.

• The old math said: "The walls might push you out, but maybe not far enough to escape the box completely."
• Zhang's math says: "If the walls are built according to the 100 Euro rule, there is always a way to push back hard enough to escape the box in every direction."

He calls this an "Escape Theorem." He proved that no matter how you arrange the walls (as long as they follow the sum rule), you can always find a direction where you can break free.

The Bigger Picture: A Unified Theory

The paper doesn't just solve the "Cube" version (the 100 Euro Conjecture). It also solves a "Round" version (the 200 Euro Conjecture, which deals with circles/spheres instead of cubes).

Think of it like this:

• The Cube (100 Euro): You are in a square room.
• The Circle (200 Euro): You are in a round room.
• Zhang's Solution: He created a "Universal Key" (an $\ell_p$-family of statements) that opens both the square room and the round room, and every shape in between.

Why Does This Matter?

1. It Settles a 30-Year Debate: It confirms a famous guess made by mathematician S. M. Rump in 1997.
2. It Improves Safety Estimates: In engineering and computer science, we often need to know if a system is stable or if it will "blow up." This theorem gives us a much tighter, more accurate safety guarantee.
3. It Connects Dots: It shows that problems that looked different (squares vs. circles) are actually just different views of the same underlying geometric truth.

Summary

Teng Zhang took a 30-year-old math riddle about whether a specific type of number grid always has a "strong" solution. By reimagining the problem as a game of cutting cheese with planks, he proved that yes, a strong solution always exists. He didn't just solve the puzzle; he built a master key that solves a whole family of similar puzzles at once.

The Bottom Line: If you build a system where every part has a specific amount of "weight," you can always find a way to make the whole system work together powerfully. The 100 Euro Conjecture is now officially Proven.

Technical Summary

Here is a detailed technical summary of the paper "Proof of 100 Euro Conjecture" by Teng Zhang.

1. Problem Statement

The paper addresses the 100 Euro Conjecture, a problem in matrix theory and functional analysis that has remained open for nearly 30 years since its formulation by S. M. Rump in 1997.

• The Conjecture: Let $A \in \mathbb{R}^{n \times n}$ be a real matrix such that the entrywise absolute value matrix $|A|$ satisfies $|A|e = ne$, where $e = (1, \dots, 1)^T$ is the all-ones vector. The conjecture asserts that there exists a nonzero vector $x \in \mathbb{R}^n$ such that:
  $$|Ax| \geq |x|$$
  (where the inequality holds entrywise).
• Geometric Interpretation: The condition $|A|e = ne$ implies that each row of $A$ lies on the boundary of the $\ell_1$-ball of radius $n$ (the cross-polytope). The conjecture asks if such a matrix necessarily possesses a "sign-real spectral radius" $\xi(A) \geq 1$.
• Previous Status: Prior to this work, the best known general bound (Rump, 1997) was $|Ax| \geq \frac{1}{3+2\sqrt{2}}|x|$. A stronger version, the 200 Euro Conjecture (Bünger & Seeger, 2024), proposed a condition based on $\ell_2$-norms of rows, which implies the 100 Euro Conjecture.

2. Methodology

The author employs a geometric approach rooted in Ball's Plank Theorem, reformulated for finite-dimensional Banach spaces.

• Core Tool: The paper utilizes a finite-dimensional reformulation of Ball's Plank Theorem (Theorem 2.1). This theorem states that for a set of linear functionals $\phi_i$ with unit norm and weights $w_i$ summing to 1, there exists a point $x$ in the unit ball such that $|\phi_i(x) - m_i| \geq w_i$.
• Renormalization: The author derives a "renormalized affine consequence" (Corollary 2.2). This allows the application of the plank theorem to arbitrary non-zero functionals $f_i$ and weights $\lambda_i$, provided $\sum \frac{\lambda_i}{\|f_i\|} \leq 1$.
• Application to Matrix Rows:
  • The problem is mapped to the Banach space $X = (\mathbb{R}^n, \|\cdot\|_p)$.
  • The rows of matrix $A$ are treated as linear functionals $f_i(x) = (Ax)_i$.
  • The dual norms of these functionals are identified: for the $\ell_p$ space, the dual norm of a row vector $r_i$ is its $\ell_q$-norm (where $1/p + 1/q = 1$).
• Diagonal Rescaling and Submatrices: To connect the row-wise conditions to the spectral radius, the author uses:
  • Diagonal Similarity Invariance: Proving that $\xi(D^{-1}AD) = \xi(A)$ for invertible diagonal $D$.
  • Irreducible Submatrices: Using the Frobenius normal form to reduce the problem to irreducible principal submatrices, allowing the application of the Perron-Frobenius theorem.

3. Key Contributions and Results

A. Proof of the 100 Euro Conjecture (Theorem 1.4 & Corollary 1.5)

The author proves a "Cube-Escape Principle" tailored to the $\ell_\infty$ norm (the cube).

• Theorem 1.4: If the $\ell_1$-norm of every row $r_i$ of $A$ satisfies $\|r_i\|_1 \geq nt$ for some $t > 0$, then there exists $x \in [-1, 1]^n$ such that $|Ax| \geq t e \geq t|x|$.
• Result: By setting $t=1$, the condition $|A|e = ne$ (which implies $\|r_i\|_1 = n$) guarantees the existence of a nonzero $x$ such that $|Ax| \geq |x|$. This confirms Conjecture 1.1.

B. Spectral Radius Comparison (Theorem 1.6)

The paper establishes a global comparison between the sign-real spectral radius $\xi(A)$ and the standard spectral radius of the absolute value matrix $\rho(|A|)$.

• Result: For any $A \in \mathbb{R}^{n \times n}$,
  $$\rho(|A|) \leq n \xi(A)$$
• Significance: This proves [3, Conjecture 21] by Bünger and Seeger, establishing that the set of matrices with $\xi(A) \geq 1$ contains the set of matrices where the spectral radius of $|A|$ is bounded by $n$.

C. Unified $\ell_p$-Escape Statement (Theorem 1.8)

The methodology is generalized to a unified family of theorems for any $p \in [1, \infty]$.

• Theorem 1.8: If the $\ell_q$-norm of every row satisfies $\|r_i\|_q \geq nt$ (where $q$ is the conjugate of $p$), then there exists $y$ with $\|y\|_p \leq 1$ such that $|Ay| \geq t e \geq t|y|$.
• Special Cases:
  • $p=\infty$ ($q=1$): Recovers the proof of the 100 Euro Conjecture.
  • $p=2$ ($q=2$): Yields a Euclidean version. If $\|r_i\|_2 \geq \sqrt{n}$, then $|Ay| \geq \frac{1}{\sqrt{n}}e$.
  • Weak 200 Euro Conjecture: By choosing specific parameters, the author derives a quantitative weak form of the 200 Euro Conjecture (Corollary 1.10). If $\|r_i\|_2 \geq \sqrt{n-1}$, then there exists $x$ such that $|Ax| \geq \frac{\sqrt{n-1}}{n}|x|$.

4. Significance

• Resolution of a Long-Standing Open Problem: The paper definitively solves the 100 Euro Conjecture, a problem that had resisted proof for three decades despite significant efforts by experts like Rump, Bünger, and Seeger.
• Unification of Geometric Inequalities: By framing the problem through Ball's Plank Theorem in $\ell_p$ spaces, the author unifies the "cube" (entrywise) and "Euclidean" (norm-based) versions of the problem, revealing a deeper structural connection between them.
• Advancement of Sign-Real Spectral Radius Theory: The results provide sharp bounds for the sign-real spectral radius $\xi(A)$, improving upon previous estimates and settling conjectures regarding the relationship between $\xi(A)$ and $\rho(|A|)$.
• Methodological Innovation: The use of finite-dimensional plank theorems combined with diagonal rescaling offers a powerful new toolkit for analyzing entrywise inequalities in matrix theory.

In summary, Teng Zhang provides a rigorous proof of the 100 Euro Conjecture by leveraging geometric functional analysis, specifically Ball's Plank Theorem, to establish the existence of vectors satisfying specific entrywise inequalities under row-norm constraints.