Skip to content

Erdős problem 481

Let a1,,ar,b1,,brNa_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)1jn,1ir.(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

Browse retained paths and inspect the exact material available for this Problem.

1 retained statement2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

481.lean

Retained formal statement1 of 1

Let a1,,ar,b1,,brNa_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)1jn,1ir.(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

Search problems.science

Find a Problem, Result, source, or page