5
$\begingroup$

I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an infinite arithmetic progression, and I bumped into the following problem:

Say we have a finite bases set $B$ of natural numbers and a finite set of tuples $T=\{(m_1, a_1), \dots, (m_t, a_t)\}$ with $m_i \in \mathbb{N}^+$ and $a_i \in \mathbb{N}$ for all $i\in\{1,\dots, t\}$, can we decide if the following set $S$ contains an infinite arithmetic progression: $$S_0 = B$$ $$S_{i+1} = S_i \cup \big\{ s \mid s = n * m_j + a_j \text{ for some } n \in S_i, 1 \leq j \leq t\big\}$$ $$S = \bigcup_{j\in\mathbb{N}} S_j$$

Edit2: This is a decision problem and goes like this: For given finite $B$ and $T$, can we decide whether $S$ contains an infinite arithmetic progression? And if we can, how?

Any ideas are appreciated :)

Edit1: I don’t know if it makes the problem more interesting or easier but I actually have an additional constraint: For each $i$, $m_i$ is a power of $2$ and $a_i < m_i$.

Improve this question
$\endgroup$
12
  • 8
    $\begingroup$ Isn't the set $S$ you have written down finite, and thus never contains an infinite arithmetic progression? Probably I have misunderstood or you meant to write something else... $\endgroup$
    – Will Sawin
    Commented Sep 7, 2021 at 17:00
  • $\begingroup$ Also, unless $k=t=1$, the conditions $1\ge i\ge k$ and $1\ge j\ge t$, which imply $k\le1$ and $t\le1$, respectively, don't make sense. This question needs some careful rewriting. $\endgroup$
    – Gerry Myerson
    Commented Sep 8, 2021 at 3:08
  • $\begingroup$ Yes, I am very sorry. I have edited it. $\endgroup$
    – Irmak Sağlam
    Commented Sep 8, 2021 at 9:21
  • 1
    $\begingroup$ I think that the condition you describe on $S$ is "$2$-recognizable"? $\endgroup$
    – aorq
    Commented Sep 8, 2021 at 14:12
  • 2
    $\begingroup$ A necessary condition is that the set $S$ have positive density, which I think is equivalent to the claim that every string of bits is a subsequence of a string of bits obtained by concatenating the $a_i$. This is not sufficient. For example, we can take $B$ to consisting of only $3$, $t=2$, $(m_1,a_1)=(2,0)$, $(m_2,a_2)=2,1$. Then $S$ is all numbers whose second bit in their binary expansion is $1$, which does not contain an infinite arithmetic progression. $\endgroup$
    – Will Sawin
    Commented Sep 8, 2021 at 14:14

0

Reset to default

You must log in to answer this question.