Skip to content

Erdős problem 481

Let a1,…,ar,b1,…,br∈Na_1,\ldots,a_r,b_1,\ldots,b_r\in \mathbb{N} such that ∑i1ai>1\sum_{i}\frac{1}{a_i}>1. For any finite sequence of nn (not necessarily distinct) integers A=(x1,…,xn)A=(x_1,\ldots,x_n) let T(A)T(A) denote the sequence of length rnrn given by (aixj+bi)1≤j≤n,1≤i≤r.(a_ix_j+b_i)_{1\leq j\leq n, 1\leq i\leq r}. Prove that, if A1=(1)A_1=(1) and Ai+1=T(Ai)A_{i+1}=T(A_i), then there must be some AkA_k with repeated elements.

Sources

The source's own material, retained exactly.

1 retained statement36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

481.lean

Retained formal statement1 of 1

Let a1,…,ar,b1,…,br∈Na_1,\ldots,a_r,b_1,\ldots,b_r\in \mathbb{N} such that ∑i1ai>1\sum_{i}\frac{1}{a_i}>1. For any finite sequence of nn (not necessarily distinct) integers A=(x1,…,xn)A=(x_1,\ldots,x_n) let T(A)T(A) denote the sequence of length rnrn given by (aixj+bi)1≤j≤n,1≤i≤r.(a_ix_j+b_i)_{1\leq j\leq n, 1\leq i\leq r}. Prove that, if A1=(1)A_1=(1) and Ai+1=T(Ai)A_{i+1}=T(A_i), then there must be some AkA_k with repeated elements.

This is true. This appears to have first been shown by Klarner [Kl82], with a generalisation given by Kolpakov and Talambutsa [KoTa22]. Essentially the same proof was found independently by Barreto in the comment section.

FormalConjectures/ErdosProblems/481.leanErdos481.erdos_4811 lineExact file
∀ {r : ℕ} (a b : Fin r → ℕ), (∀ (i : Fin r), 0 < a i) → 1 < ∑ i, 1 / ↑(a i) → ∃ k, ¬((Erdos481.T a b)^[k] [1]).Nodup
SolvedStatement only, no proof