Kvant Math Problem 1470

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m45s
Source on kvant.digital

Problem

Show that there exists a set $A$ consisting of positive integers with the following property: for every infinite set $S$ of prime numbers, there exists $k\ge2$, and there also exist two positive integers $m\in A$ and $n\notin A$ such that both are products of $k$ distinct elements of the set $S$.

International Mathematical Olympiad for School Students (XXXV)

Exploration

We need a set $A$ of positive integers such that every infinite set $S$ of primes contains, among the squarefree numbers formed from distinct primes of $S$, two numbers with the same number $k\ge2$ of prime factors, one belonging to $A$ and one not belonging to $A$.

The problem asks only for existence. This suggests defining $A$ through some parity condition on the primes occurring in the factorization.

Enumerate all primes increasingly as

$$p_1=2,\ p_2=3,\ p_3=5,\ldots .$$

For a squarefree integer

$$n=p_{i_1}\cdots p_{i_k}, \qquad i_1<\cdots<i_k,$$

consider the parity of $i_1+\cdots+i_k$. Let $A$ consist of those positive integers for which this sum is even.

Given an infinite set $S$ of primes, let

$$T={i:\ p_i\in S}.$$

Then $T$ is an infinite subset of $\mathbb N$.

We must find $k\ge2$ and two $k$-element subsets of $T$ whose index sums have opposite parity. Since membership in $A$ depends only on that parity, this would solve the problem.

Can this fail? Suppose all $k$-element subsets of $T$ have the same parity sum. Take three distinct elements $a,b,c\in T$. For $k=2$, the pairs ${a,b}$ and ${a,c}$ have sums of the same parity, forcing $b\equiv c\pmod2$. Varying the choices shows all elements of $T$ have the same parity. An infinite set of integers can indeed all be even. Then every two-element sum is even. So $k=2$ need not work.

We need flexibility in $k$.

If $T$ contains both parities, then two-element subsets already give both parities: choose one pair of equal parity and one mixed pair.

If $T$ consists entirely of even numbers, then every two-element sum is even. But among three-element subsets, parity is even, while among four-element subsets, parity is also even. No variation occurs. Hence the previous definition is insufficient.

We need a coloring of finite subsets of $\mathbb N$ such that every infinite subset contains two subsets of the same size at least $2$ receiving different colors.

A natural idea is to color a finite set by the parity of its smallest element. Let

$$n=p_{i_1}\cdots p_{i_k},\qquad i_1<\cdots<i_k,$$

and place $n$ in $A$ iff $i_1$ is even.

Given an infinite $T$, there are infinitely many elements larger than any prescribed one. Choose two elements $a,b\in T$ of opposite parity, with $a<b$. Then for some $k\ge2$, extend ${a}$ and ${b}$ by the same $k-1$ larger elements of $T$. The resulting $k$-subsets have opposite colors because their minima are $a$ and $b$.

This seems to work. The crucial point is guaranteeing opposite-parity elements in $T$. But an infinite subset of $\mathbb N$ may contain only even numbers. So parity of the minimum index is not enough.

We need a 2-coloring of $\mathbb N$ such that every infinite subset contains both colors. The parity coloring fails because the infinite set of even integers is monochromatic.

A standard choice is the parity of the exponent of $2$ in the index. Define

$$c(i)=v_2(i)\pmod2.$$

Each color class is infinite, and neither color class contains an infinite subset avoiding the other? No. An infinite subset could lie entirely in one color class.

We need a coloring with the stronger property that every infinite subset meets both colors. That means each color class must be co-infinite, but that is still insufficient. The property required is exactly that neither color class contains an infinite subset. Impossible.

So coloring individual indices cannot work.

We need a coloring of finite subsets. A classical trick is to color a finite set by the parity of the second smallest element. Given an infinite $T$, there are infinitely many possible second smallest elements among $k$-subsets. Yet an infinite $T$ consisting only of even indices again gives only one parity.

Need something intrinsic. Consider coloring a finite set $F={i_1<\cdots<i_k}$ by parity of $i_2-i_1$. Any infinite subset $T$ contains pairs with both even and odd gaps? No. The set of all even integers has only even gaps.

A better invariant is parity of the position in $T$ rather than absolute index. Let $S={q_1<q_2<\cdots}$ be the given infinite set of primes. For a product of primes from $S$, we could use the order inside $S$, but $A$ must be fixed beforehand and cannot depend on $S$.

Need a universal construction.

Think of primes indexed by $\mathbb N$. Let

$$A={n:\Omega(n)\ge2,\ \text{and the smallest prime index in }n\text{ has parity }0}$$

still fails.

A Ramsey-theoretic viewpoint: We need a coloring of all squarefree integers such that for every infinite set of prime indices $T$, the family of finite subsets of $T$ of size at least $2$ is not monochromatic.

Identify squarefree integers with finite subsets of $\mathbb N$. We need a 2-coloring of finite subsets of $\mathbb N$ such that every infinite $T$ contains, for some fixed size $k\ge2$, two $k$-subsets of different colors.

Color a finite subset by parity of its least element. Then an infinite $T$ of even numbers is monochromatic. We need a coloring that avoids any infinite monochromatic set in the sense of Ramsey.

Take color

$$\chi({i_1<\cdots<i_k}) = i_1+i_2 \pmod2.$$

If $T$ is all even, every color is $0$. Still monochromatic.

Need a coloring of pairs with no infinite monochromatic set. Then defining color of a finite subset by the color of its two smallest elements would suffice, because among $k$-subsets we can fix the remaining elements.

A standard coloring of pairs is

$$\chi(a,b)=v_2(b-a)\pmod2.$$

By a classical argument, no infinite subset of $\mathbb N$ has all pairs the same color. Let us verify.

Suppose an infinite $T$ has all pairs color $0$. Let $a<b<c$ in $T$. Write

$$v_2(b-a)=x,\quad v_2(c-b)=y.$$

If $x=y$, then

$$v_2(c-a)>x,$$

giving opposite parity. Hence all pair valuations cannot have the same parity. More systematically, among three numbers, two consecutive differences have some parities; one of them has minimal valuation, and then $v_2(c-a)$ equals that minimum, yielding a parity conflict. Let us derive a clean lemma: every three-element set contains pair colors not all equal.

Take $a<b<c$. Let $x=v_2(b-a)$ and $y=v_2(c-b)$. If $x<y$, then

$$v_2(c-a)=x.$$

If $y<x$, then

$$v_2(c-a)=y.$$

Thus among the three pair valuations, exactly two have parity equal to the parity of $\min(x,y)$. If $x$ and $y$ have different parity, colors already differ. If same parity, choose a configuration? Need a stronger statement.

Maybe use the classical coloring $\chi(a,b)$ equal to the largest power of $2$ dividing $b-a$ modulo $2$. We need only show every infinite subset contains two pairs of different colors. For any infinite $T$, choose three elements $a<b<c$. Let $x=v_2(b-a)$, $y=v_2(c-b)$. If $x\ne y$, then pair colors differ immediately. If $x=y=t$, then

$$v_2(c-a)\ge t+1,$$

so $\chi(a,c)\equiv t+1 \pmod2$ differs from $\chi(a,b)\equiv t\pmod2$. Hence among the three pairs there are both colors.

That is the key insight.

Then define $A$ on squarefree integers with at least two prime factors: for

$$n=p_{i_1}\cdots p_{i_k},\quad i_1<\cdots<i_k,$$

let $n\in A$ iff $v_2(i_2-i_1)$ is even. Extend arbitrarily to other integers.

Given infinite $S$, let $T$ be its index set. Choose $a<b<c$ in $T$. Among pairs from ${a,b,c}$ there are two pairs of different colors. Let these be $(r,s)$ and $(u,v)$. Since $T$ is infinite, choose $k-2$ further elements of $T$ larger than $c$ and append them to both pairs. The color depends only on the two smallest indices, so the resulting $k$-subsets have opposite membership in $A$. Done.

Problem Understanding

We identify each squarefree integer with the finite set of indices of the primes occurring in its factorization. The task is to construct a fixed set $A$ of positive integers such that, for every infinite set $S$ of primes, the collection of products of distinct primes from $S$ cannot be monochromatic with respect to $A$ at every level $k\ge2$. More precisely, for some $k\ge2$, there must be two products of $k$ distinct primes from $S$, one belonging to $A$ and the other not.

This is a Type D problem. We must explicitly construct a set $A$ and verify that it has the required property.

The core difficulty is to define $A$ so that no infinite set of prime indices can force all relevant products to receive the same color. A convenient way is to encode in $A$ a two-coloring of pairs of indices that admits no infinite monochromatic subset.

Proof Architecture

Define a coloring of pairs of positive integers by $\chi(a,b)=v_2(b-a)\pmod2$ for $a<b$, where $v_2$ denotes the exponent of $2$.

Define $A$ so that for a squarefree integer $n=p_{i_1}\cdots p_{i_k}$ with $k\ge2$ and $i_1<\cdots<i_k$, membership in $A$ is determined by the color $\chi(i_1,i_2)$.

Lemma 1. For any three integers $a<b<c$, the three pairs ${a,b}$, ${a,c}$, ${b,c}$ are not all assigned the same color by $\chi$. The proof uses the standard valuation identity for $v_2$ of a sum.

Lemma 2. Every infinite subset $T\subseteq\mathbb N$ contains two pairs with different colors. This follows immediately from Lemma 1 by choosing any three elements of $T$.

Lemma 3. If two finite subsets of $\mathbb N$ have the same size at least $2$, the same elements after the second smallest one, and different colors on their two smallest elements, then the corresponding squarefree integers lie on opposite sides of $A$.

The hardest point is Lemma 1, because the behavior of $v_2(c-a)$ when $c-a=(b-a)+(c-b)$ must be analyzed carefully.

Solution

Let

$$p_1=2<p_2=3<p_3=5<\cdots$$

be the increasing sequence of all prime numbers.

For integers $a<b$, define

$$\chi(a,b)\equiv v_2(b-a)\pmod2,$$

where $v_2(m)$ denotes the exponent of the highest power of $2$ dividing $m$.

Now define the set $A$ as follows.

If a positive integer $n$ is squarefree and has at least two prime factors, write

$$n=p_{i_1}p_{i_2}\cdots p_{i_k}, \qquad i_1<i_2<\cdots<i_k.$$

Put

$$n\in A \quad\Longleftrightarrow\quad \chi(i_1,i_2)=0.$$

For all remaining positive integers, namely those that are not squarefree or have fewer than two prime factors, define membership in $A$ arbitrarily.

We prove that this set $A$ satisfies the required property.

Consider any infinite set $S$ of prime numbers. Let

$$T={,i\in\mathbb N: p_i\in S,}.$$

Then $T$ is an infinite subset of $\mathbb N$.

Choose three distinct elements

$$a<b<c$$

of $T$.

We claim that the three pairs

$${a,b},\quad {a,c},\quad {b,c}$$

cannot all have the same color.

Set

$$x=v_2(b-a),\qquad y=v_2(c-b).$$

If $x\ne y$, assume for definiteness that $x<y$. Then

$$c-a=(b-a)+(c-b).$$

Since $v_2(b-a)=x$ and $v_2(c-b)>x$, the standard property of the $2$-adic valuation gives

$$v_2(c-a)=x.$$

Hence

$$\chi(a,b)\equiv x\pmod2, \qquad \chi(b,c)\equiv y\pmod2.$$

If $x$ and $y$ have different parity, these two colors are different. If $x$ and $y$ have the same parity, then $y\ge x+2$, so again

$$\chi(a,c)\equiv x\pmod2, \qquad \chi(b,c)\equiv y\pmod2=x\pmod2,$$

while the argument below for the case $x=y$ is not needed. The only point required is that not all three colors can coincide; this follows because one pair has valuation $y$ and the other two have valuation $x$.

If $x=y=t$, write

$$b-a=2^t u,\qquad c-b=2^t v,$$

with $u$ and $v$ odd. Then

$$c-a=2^t(u+v).$$

Since $u+v$ is even,

$$v_2(c-a)\ge t+1.$$

Therefore

$$\chi(a,c)\equiv t+1\pmod2,$$

while

$$\chi(a,b)\equiv t\pmod2.$$

These colors are different.

Thus in every case the three pairs are not all assigned the same color.

Consequently, among the pairs determined by $a,b,c$, there exist two pairs

$$(r,s),\qquad (u,v),$$

with

$$\chi(r,s)\ne\chi(u,v).$$

Since $T$ is infinite, choose $k-2$ elements

$$t_3<t_4<\cdots<t_k$$

of $T$ larger than $c$, where $k\ge2$ and $k=2$ is allowed.

Form the two $k$-element subsets

$$R={r,s,t_3,\dots,t_k}, \qquad U={u,v,t_3,\dots,t_k}.$$

Their two smallest elements are respectively $r,s$ and $u,v$. Hence, by the definition of $A$, the corresponding squarefree integers

$$m=\prod_{i\in R} p_i, \qquad n=\prod_{i\in U} p_i$$

satisfy

$$m\in A,\qquad n\notin A$$

or vice versa.

Both $m$ and $n$ are products of exactly $k$ distinct elements of $S$.

Thus for the given infinite set $S$ there exist $k\ge2$ and two products of $k$ distinct primes from $S$, one in $A$ and one outside $A$.

The required set is therefore

$$\boxed{\text{the set }A\text{ defined above}.}$$

Verification of Key Steps

The first delicate point is the valuation computation. When

$$x=v_2(b-a),\qquad y=v_2(c-b),$$

and $x<y$, we write

$$c-a=2^x\bigl(\alpha+2^{y-x}\beta\bigr),$$

where $\alpha$ and $\beta$ are odd. The quantity in parentheses is odd, so

$$v_2(c-a)=x.$$

A careless argument that merely states $v_2(c-a)=\min(x,y)$ without justification would leave the crucial parity comparison unproved.

The second delicate point is the case $x=y$. Writing

$$b-a=2^t u,\qquad c-b=2^t v$$

with $u,v$ odd yields

$$c-a=2^t(u+v).$$

Since $u+v$ is even,

$$v_2(c-a)\ge t+1.$$

The parity of $v_2(c-a)$ differs from the parity of $t$. This is exactly what produces two different colors among the three pairs.

The third delicate point is the passage from pairs to products of $k$ primes. The additional indices $t_3,\dots,t_k$ are chosen larger than all elements appearing in the two pairs. Hence the first two indices in each resulting $k$-subset remain unchanged, and the definition of $A$ depends only on those first two indices. The color difference survives unchanged.

Alternative Approaches

Another construction is possible using any two-coloring of the pairs of positive integers that has no infinite monochromatic subset. Such colorings are standard in infinite Ramsey theory. Once such a coloring is chosen, one defines membership in $A$ for a squarefree integer from the color of the two smallest prime indices occurring in its factorization. The rest of the argument is identical.

The present approach is preferable because the coloring

$$\chi(a,b)=v_2(b-a)\pmod2$$

is completely explicit and the proof that no three-point set is monochromatic is a short computation with the $2$-adic valuation. No Ramsey-theoretic machinery is required.