IMO 1994 Problem 6

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 3m33s

Problem

Show that there exists a set $A$ of positive integers with the following property: For any infinite set $S$ of primes there exist two positive integers $m \in A$ and $n \not\in A$ each of which is a product of $k$ distinct elements of $S$ for some $k \ge 2$.

Exploration

For any infinite set $S$ of primes, the objects under consideration are integers of the form $p_1p_2\cdots p_k$, where $p_i\in S$ are distinct primes and $k\ge 2$. Such numbers are precisely the squarefree integers whose prime factors lie in $S$, excluding primes themselves.

The requirement is to construct a fixed set $A\subset \mathbb{Z}_{>0}$, independent of $S$, such that every infinite $S$ produces at least one such product in $A$ and at least one such product outside $A$.

A natural invariant on squarefree integers is the number of distinct prime factors. This quantity changes predictably when passing from products of $k$ primes to products of $k+1$ primes. Since every infinite set of primes contains arbitrarily large finite subsets, it is always possible to form products with different values of this invariant.

The main difficulty is ensuring that the definition of $A$ does not depend on $S$, while still guaranteeing that every infinite $S$ forces a split between $A$ and its complement among these products.

A promising approach is to separate integers according to the parity of the number of distinct prime factors.

Problem Understanding

This is a Type D problem, requiring the explicit construction of a set $A$ of positive integers with a universal splitting property over all infinite prime sets.

We must define $A$ once and for all, then show that for every infinite set of primes $S$, there exist two integers formed from distinct primes in $S$, each using at least two primes, such that one lies in $A$ and the other does not.

The core difficulty is universality: the same fixed set $A$ must work simultaneously for every infinite $S$, even though $S$ is arbitrary.

The construction will classify integers according to the parity of the number of distinct prime factors. The intuition is that any infinite $S$ contains subsets of size $2$ and $3$, producing products whose factor counts differ in parity.

We define

$$A = {n\in \mathbb{Z}_{>0} : \omega(n)\ \text{is even}},$$

where $\omega(n)$ denotes the number of distinct prime divisors of $n$.

Proof Architecture

The proof will consist of the following components.

Lemma 1 states that for any infinite set of primes $S$, there exist at least two distinct primes in $S$, hence a product of two distinct elements of $S$ exists. This follows directly from infinitude.

Lemma 2 states that for any infinite set of primes $S$, there exist at least three distinct primes in $S$, hence a product of three distinct elements of $S$ exists. This again follows from infinitude.

Lemma 3 states that if $n$ is a product of $k$ distinct primes, then $\omega(n)=k$. This follows from the definition of $\omega$ and squarefreeness.

Lemma 4 states that in any infinite set $S$, there exist integers $m$ and $n$ formed from distinct primes in $S$ with $\omega(m)=2$ and $\omega(n)=3$. This is the key structural lemma producing opposite parities.

The hardest step is Lemma 4, since it combines existence of sufficiently large finite subsets of $S$ with the behavior of $\omega$.

Solution

Lemma 1

For any infinite set $S$ of primes, there exist two distinct primes $p,q\in S$.

Since $S$ is infinite, it contains at least one element $p$. Removing $p$ still leaves an infinite set, hence nonempty, so there exists $q\in S$ with $q\ne p$.

This establishes the existence of two distinct primes in $S$.

Certification: this step ensures that every infinite set of primes contains a subset of size $2$, and failure would contradict infinitude.

Lemma 2

For any infinite set $S$ of primes, there exist three distinct primes $p,q,r\in S$.

After selecting distinct primes $p,q\in S$ from Lemma 1, the set $S\setminus{p,q}$ remains infinite and hence nonempty. Choosing any $r$ in this remaining set yields three distinct primes.

Certification: this step guarantees the existence of subsets of size $3$ inside any infinite set of primes, and it relies only on infinitude.

Lemma 3

If $n=p_1p_2\cdots p_k$ with $p_1,\dots,p_k$ distinct primes, then $\omega(n)=k$.

Each prime divisor of $n$ must be among $p_1,\dots,p_k$, since the prime factorization of integers is unique. Conversely, each $p_i$ divides $n$, so all $k$ primes are distinct prime divisors of $n$. Therefore the number of distinct prime divisors equals $k$.

Certification: this identifies $\omega(n)$ exactly for squarefree products, preventing any hidden multiplicity errors.

Lemma 4

For any infinite set $S$ of primes, there exist integers $m$ and $n$ formed as products of distinct elements of $S$ with $\omega(m)=2$ and $\omega(n)=3$.

By Lemma 1, choose distinct primes $p,q\in S$ and define $m=pq$. By Lemma 3, $\omega(m)=2$.

By Lemma 2, choose distinct primes $r,s,t\in S$ and define $n=rst$. By Lemma 3, $\omega(n)=3$.

Certification: this constructs two squarefree elements of $S$-generated integers whose values of $\omega$ have different parity, which is the structural mechanism needed for separation.

Construction of $A$

Define

$$A = {n\in \mathbb{Z}_{>0} : \omega(n)\equiv 0 \pmod{2}}.$$

Verification

Let $S$ be any infinite set of primes. By Lemma 4, there exist integers $m=pq$ and $n=rst$ with $p,q,r,s,t\in S$ distinct primes.

For $m$, $\omega(m)=2$, hence $m\in A$ since $2$ is even.

For $n$, $\omega(n)=3$, hence $n\notin A$ since $3$ is odd.

Both $m$ and $n$ are products of $k$ distinct elements of $S$ with $k\ge 2$, satisfying the required form.

This establishes that every infinite $S$ contains such a pair $(m,n)$ with opposite membership in $A$.

Verification of Key Steps

The critical point is the extraction of three distinct primes from an arbitrary infinite set $S$. This relies on the fact that removing finitely many elements from an infinite set leaves it nonempty; applying this twice ensures availability of three distinct primes.

Another delicate point is the identification $\omega(p_1p_2p_3)=3$. Any oversight involving repeated primes would break this equality, but the construction explicitly uses distinct primes, ensuring squarefreeness.

The final check is independence from $S$. The definition of $A$ depends only on $\omega(n)$ and not on the chosen prime set, so no hidden dependence on $S$ occurs.

Alternative Approaches

A different approach encodes integers by the parity of the total number of prime factors with multiplicity, leading to similar constructions. Another method uses additive structures over the vector space over $\mathbb{F}_2$ generated by primes, interpreting membership in $A$ as a linear functional on exponent vectors. Both approaches ultimately reduce to enforcing a parity split on squarefree products from any infinite set of primes, but the present solution is shorter because it uses only the basic invariant $\omega(n)$.