we-solve (beta)

Math-542 · mathematics · Combinatorics

Rado's Boundedness Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

The equation is $a_1x_1+\cdots+a_kx_k=0$ in positive integers. Rado's single-equation condition is that some nonempty subset of the coefficients sums to zero. When this fails, $c(a_1,\ldots,a_k)$ is the least number of colours in a colouring of ${\mathbb{N}}$ with no monochromatic solution. The target is a finite bound $C(k)$ independent of all coefficient magnitudes. [S1] [S2]

Statement recorded in the supplied source.
Suppose $a_1, \dots, a_k$ are integers which do not satisfy Rado's condition. Is $c(a_1, \dots, a_k)$ bounded in terms of $k$ only? [S1]
Residual task reported by the archive.

The embedded review (2026-08-17) records: Prove a coefficient-independent bound for each k>=4 or find a counterexample. [S1]

Short English statement

For a linear equation that can be avoided by colouring the positive integers, is a bounded number of colours enough when only the number of variables is fixed?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-542-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-542

Rado's Boundedness Conjecture

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

The equation is $a_1x_1+\cdots+a_kx_k=0$ in positive integers. Rado's single-equation condition is that some nonempty subset of the coefficients sums to zero. When this fails, $c(a_1,\ldots,a_k)$ is the least number of colours in a colouring of ${\mathbb{N}}$ with no monochromatic solution. The target is a finite bound $C(k)$ independent of all coefficient magnitudes. [S1] [S2]

Statement recorded in the supplied source.
Suppose $a_1, \dots, a_k$ are integers which do not satisfy Rado's condition. Is $c(a_1, \dots, a_k)$ bounded in terms of $k$ only? [S1]
Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove a coefficient-independent bound for each k>=4 or find a counterexample. [S1]

Short English statement

For a linear equation that can be avoided by colouring the positive integers, is a bounded number of colours enough when only the number of variables is fixed?

Research attempt

Provenance and scope.
This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.
Formal target and source scope.
The coefficients $a_1,\ldots,a_k$ have no nonempty zero-sum subcollection. We seek a colouring of the positive integers with no monochromatic solution to $\sum a_ix_i=0$, using a number of colours bounded only by $k$. The cited Fox--Kleitman work is relevant to coefficient-independent bounds in small numbers of variables; no uninspected numerical bound from it is used here. The elementary construction below gives an explicit coefficient-dependent bound and solves the two-variable case with two colours, making the remaining uniformity issue precise.
A complete leading-digit colouring.
Choose a prime $p$ dividing none of the nonempty subset sums $s_I=\sum_{i\in I}a_i$. This is possible because they are finitely many nonzero integers. Colour a positive integer $x$ by its leading nonzero $p$-adic digit \[ c(x)=p^{-v_p(x)}x\pmod p\in{\mathbb{F}}_p^*. \] There are $p-1$ colours. Suppose all $x_i$ have the same colour $c$ and satisfy the equation. Let $v=\min_i v_p(x_i)$ and $I=\{i:v_p(x_i)=v\}$. Divide the equation by $p^v$ and reduce modulo $p$. Terms outside $I$ vanish, while each remaining unit is $c$. Thus \[ c\sum_{i\in I}a_i=0\pmod p. \] Since $c\ne0$, this contradicts the choice of $p$. The argument allows repeated values among the $x_i$ and treats negative coefficients without alteration. A zero coefficient cannot occur under the hypothesis, because its singleton would be a zero-sum subcollection.
An explicit bound and the dependence that matters.
Put $M=\max_i|a_i|$ and $P=\prod_{\varnothing\ne I\subseteq[k]}|s_I|$. Every factor is positive and at most $kM$, so $1\leq P\leq(kM)^{2^k-1}$. Any prime divisor $p$ of $P+1$ is coprime to $P$, and therefore divides no subset sum. The previous colouring consequently uses at most \[ p-1\leq P\leq(kM)^{2^k-1} \] colours. This proves finiteness constructively and quantifies its coefficient dependence. It does not answer the question, whose whole point is to remove $M$. Replacing the prime by a supposedly bounded small prime without checking all subset sums would invalidate the proof.

For example, the coefficients $(1,1,-3)$ have nonzero subset sums among $\{1,2,-1,-2,-3\}$. Prime five works, giving a concrete four-colouring by the first nonzero base-five digit. This small example also shows why taking prime two or three automatically is unsafe: both divide some relevant subset sum.

The two-variable case has a uniform answer.
Consider $ax+by=0$ with $a,b$ nonzero and $a+b\ne0$. If $a,b$ have the same sign, there are no positive solutions and one colour suffices. Otherwise the equation is $y=rx$, where $r=-a/b$ is a positive rational different from one. Some prime $p$ has $t=v_p(r)\ne0$. Colour $x$ by \[ \left\lfloor\frac{v_p(x)}{|t|}\right\rfloor\pmod2. \] For any positive integer solution $y=rx$, the valuations satisfy $v_p(y)=v_p(x)+t$. Dividing by $|t|$ changes the floor by exactly $1$ or $-1$, so the two colours differ. This gives a uniform two-colouring independent of the magnitudes of $a,b$. If positive solutions exist, one colour cannot avoid them, so two is exact in the opposite-sign case. Existence of such solutions follows by clearing the positive rational ratio.
Why this valuation trick does not immediately extend.
For two variables, one equality fixes a nonzero valuation difference. With three or more variables, several lowest-valuation terms may cancel. The leading-digit construction prevents that only by excluding every possible subset sum modulo the chosen prime. A colouring recording a single valuation parity cannot distinguish all such cancellation patterns. The obstruction is not merely that a proof was omitted: the two-variable reduction has one prescribed ratio, whereas the general equation has many possible lowest-valuation index sets.
Verification and remaining gap.
The division by $p^v$ is integral, $I$ is nonempty, and reducing a common leading digit is justified exactly for the minimal-valuation terms. The explicit prime-from-$P+1$ bound remains valid when $P=1$. The two-variable colouring handles negative $t$ because subtracting one full block changes floor parity. The established results are the full coefficient-dependent construction and the optimal uniform answer for two variables. The unresolved step is a colour bound depending only on $k$ for the remaining cases, with no hidden dependence on a selected prime or coefficient size.

Sources

Go to contribution →