Erdős Problem #172

Erdős Problem 172: simultaneous finite sums and products

Statement and outcome

For a finite $A\subset\mathbb N$, let $\operatorname{FS}(A)$ and $\operatorname{FP}(A)$ consist respectively of sums and products over nonempty subsets, with no repeated elements. The question asks whether every finite colouring admits arbitrarily large $A$ for which their union has one colour.

We prove the assertion for eventually periodic colourings and for a class of simultaneous prime-valuation colourings. For arbitrary colourings we prove a canonical reduction to a finite list of colours indexed by subset size. Making that list one colour remains unresolved in this attempt.

Eventually periodic colourings

Suppose $c(n+q)=c(n)$ for all $n\ge N_0$. All sufficiently large multiples of $q$ then have a common colour. Choose any desired number of distinct multiples of $q$ at least $\max(N_0,2)$. Every nonempty sum and product is again such a multiple, so the whole union has this colour. This includes the simpler monochromatic-ideal observation in the old local attempt.

Simultaneous valuation colourings

Let $P$ be a finite nonempty set of primes, and let the colour of $n$ depend only on the tuple $(v_p(n)\bmod m_p)_{p\in P}$, for fixed positive integers $m_p$. Put $M=\operatorname{lcm}_{p\in P}m_p$, $B=\prod_{p\in P}p$, and choose \[ A=\{B^{M},B^{2M},\ldots,B^{rM}\}. \] For a nonempty subset $S$ of the exponents, its sum factors as $B^{Mj_0}(1+\sum_{j\in S,\ j>j_0}B^{M(j-j_0)})$, where $j_0=\min S$. The parenthesis is one modulo every $p\in P$. Thus each $p$-valuation of this sum is exactly $Mj_0$. The valuation of the corresponding product is $M\sum_{j\in S}j$. All these valuations are zero modulo their respective $m_p$. Hence all sums and products have the colour assigned to the zero tuple. Distinct valuations are essential here: unrestricted sums of terms of equal valuation could introduce cancellation.

A reduction valid for every finite colouring

Fix a target size $r$. There is an infinite set $B\subset\mathbb N$ and colours $\gamma_j,\delta_j$, $1\le j\le r$, such that every $j$-subset $S\subset B$ satisfies \[ c\left(\sum_{s\in S}s\right)=\gamma_j,\qquad c\left(\prod_{s\in S}s\right)=\delta_j. \tag{1} \] Apply the infinite Ramsey theorem successively for $j=1,\ldots,r$, colouring each $j$-subset by the ordered pair of displayed colours and passing to an infinite homogeneous subset. Later restrictions preserve earlier properties.

Here the needed Ramsey theorem itself follows by induction on uniformity. The case of singletons is infinite pigeonhole. For a colouring of $j$-subsets, recursively choose vertices $v_i$ and nested infinite tails so that the colour of $\{v_i\}\cup T$, for $(j-1)$-subsets $T$ of the new tail, is a fixed colour $\eta_i$; the induction hypothesis supplies that tail. Infinitely many $\eta_i$ agree. The corresponding $v_i$ form a homogeneous set, since the least-indexed member determines the colour of every $j$-subset. This proves the input and hence $1$.

Any $r$ distinct members of $B$ now have sums and products whose colours depend only on cardinality. But there are up to $2r-1$ independent entries in this profile, since only $\gamma_1=\delta_1$ is automatic. Ramsey homogeneity does not assert that these entries agree. This is the exact gap in trying to turn $1$ into the desired conclusion.

Why clearing rational denominators is insufficient

If a rational set $A$ has common denominator dividing $D$, replacing it by $DA$ changes a subset sum to $D\sum A'$ but a product of $j$ elements to $D^j\prod A'$. An arbitrary integer colouring need not preserve colours under any of these different dilations. Thus the rational analogue reported on the problem page does not transfer merely by clearing denominators.

Assessment and attribution

The old gpt_pro_5.2/172.tex handled parity and a monochromatic ideal. Those are included in the proved periodic special case; the valuation construction and cardinality-profile reduction give further explicit partial results. Source and literature context: https://www.erdosproblems.com/172. No external sums-and-products theorem is invoked as a proof, and no novelty claim is made.

COMPLETION ESTIMATE

COMPLETION: 30%

PROBLEM

Is it true that in any finite colouring of $\mathbb{N}$ there exist arbitrarily large finite $A$ such that all sums and products of distinct elements in $A$ are the same colour?

OUTPUT

1) FORMAL RESTATEMENT

Let $r\ge 1$ and let $c:\mathbb N\to\{1,2,\dots,r\}$ be a coloring.

For a finite set $A\subseteq\mathbb N$, define its finite sums set \[ \mathrm{FS}(A):=\left\{\sum_{x\in S} x: \emptyset\ne S\subseteq A\right\} \] and its finite products set \[ \mathrm{FP}(A):=\left\{\prod_{x\in S} x: \emptyset\ne S\subseteq A\right\}. \] (“Distinct elements” means we sum/product over subsets, no repetition.)

The question is:

For every $r$ and every coloring $c$, do there exist finite sets $A$ of arbitrarily large size such that $c$ is constant on $\mathrm{FS}(A)\cup \mathrm{FP}(A)$?

Equivalently: for every $m\in\mathbb N$ does there exist $A\subseteq\mathbb N$ with $|A|=m$ and a color $\gamma$ such that every nonempty subset-sum and subset-product of $A$ has color $\gamma$?

---

2) QUICK LITERATURE/CONTEXT CHECK

I will not use or claim any external results beyond what is explicitly written in the problem text.

The problem text reports:

* Hindman proved the analogous statement for an infinite $A$ is false with 7 colors. * Moreira proved that in any finite coloring of $\mathbb N$ there exist $x,y$ with $\{x,x+y,xy\}$ monochromatic. * Alweiss proved the finite-$A$ statement over $\mathbb Q\setminus\{0\}$.

I do not re-prove these results.

---

3) ATTACK PLAN

I do not currently see a purely elementary route to the full statement in $\mathbb N$ because it requires simultaneous additive and multiplicative structure.

Partial work:

1. Record basic necessary/structural observations about what it means for $\mathrm{FS}(A)\cup\mathrm{FP}(A)$ to be monochromatic. 2. Give concrete sanity-check examples for specific colorings (e.g. parity coloring) where the statement is easy.

---

4) WORK

FAST REALITY CHECK / sanity examples

* If $r=1$ (one color), the statement is trivial: any finite $A$ works. * For the 2-coloring by parity, $c(n)=n\bmod 2$, choosing $A$ to be any finite set of even integers makes all subset sums and products even (hence monochromatic).

These do not address arbitrary colorings but confirm the statement is consistent with some natural colorings.

---

Lemma 4.1 (a sufficient condition via a monochromatic ideal)

Fix a coloring $c:\mathbb N\to\{1,\dots,r\}$. If there exist a color $\gamma$ and an integer $m\ge 2$ such that \[ \forall t\in\mathbb N:\quad c(mt)=\gamma, \] then for every $M\in\mathbb N$ there exists a set $A$ with $|A|=M$ such that $c$ is constant equal to $\gamma$ on $\mathrm{FS}(A)\cup\mathrm{FP}(A)$.

Proof. Assume all multiples of $m$ have color $\gamma$. Let $A\subseteq m\mathbb N$ be any finite set of size $M$ (e.g. $A=\{m,2m,\dots,Mm\}$).

1. Every element of $\mathrm{FS}(A)$ is a sum of multiples of $m$, hence itself a multiple of $m$. 2. Every element of $\mathrm{FP}(A)$ is a product of multiples of $m$, hence itself a multiple of $m$.

Therefore $\mathrm{FS}(A)\cup\mathrm{FP}(A)\subseteq m\mathbb N$, so $c$ takes the constant value $\gamma$ on this union. $\square$

---

Lemma 4.2 (parity coloring works with even sets)

Let $c(n)=n\bmod 2$ be the 2-coloring of $\mathbb N$ into evens/odds. For every $M\in\mathbb N$, the set $A:=\{2,4,6,\dots,2M\}$ satisfies that $\mathrm{FS}(A)\cup\mathrm{FP}(A)$ is monochromatic (all even).

Proof. Every element of $A$ is divisible by $2$.

* Any finite sum of elements of $A$ is divisible by $2$. * Any finite product of elements of $A$ is divisible by $2$.

Hence every element of $\mathrm{FS}(A)\cup\mathrm{FP}(A)$ is even, so has the same color under $c$. $\square$

---

5) VERIFICATION

* Lemma 4.1 is logically correct but requires a very strong hypothesis (a whole multiplicative ideal being monochromatic), which need not hold in an arbitrary coloring. * Lemma 4.2 correctly verifies a basic sanity example. * I did not find (and did not computationally search for) an explicit finite coloring that prevents large $A$; the obstruction seems genuinely global.

---

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

I proved that the conjecture holds for any coloring in which some full set of multiples $m\mathbb N$ is monochromatic (Lemma 4.1), and verified it for the parity coloring (Lemma 4.2).

(ii) Exact first gap.

Remove the very strong hypothesis in Lemma 4.1: prove existence of large $A$ for an arbitrary finite coloring of $\mathbb N$.

(iii) Top 3 next moves (concrete targets).

1. Try to prove the statement first for $|A|=2$ (i.e. find $a,b$ with $\{a,b,a+b,ab\}$ monochromatic) or $|A|=3$ in any finite coloring. 2. Attempt a reduction to structured colorings using density/regularity or algebraic decomposition (e.g. working inside multiplicative subsemigroups). 3. Explore whether the $\mathbb Q\setminus\{0\}$ result can be transferred to $\mathbb N$ via denominators/clearing, or identify a clear obstruction.

(iv) What a minimal counterexample would likely look like.

A minimal counterexample coloring would likely avoid large monochromatic “additively closed” and “multiplicatively closed” patterns simultaneously, perhaps by encoding $p$-adic valuations or logarithmic partitions so that sums and products systematically change color.