In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open:

Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for all $n \in \mathbb{N}$. Prove or disprove that the language of the base-k representations of all integers in $\{p(n) \mid n \geqslant 0\}$ is context-free if and only if the degree of $p$ is $\leqslant 1$.

What's its status now (as for Oct 2018)? Is it proven? What about some special cases?

  • 1
    If $k = 1$ (unary representation) then even the simplest $p(n) = n^2$ is not context-free (the well known non CF language $L = \{ 1^{n^2} \}$) – Marzio De Biasi Nov 9 at 16:27
  • @MarzioDeBiasi The so-called unary representation is not base-$1$. The only integer representable in actual base-$1$ would be $0$. – Emil Jeřábek 11 hours ago

Of course $k \geq 2$ here.

There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.

As far as I know, the problem is still open. One direction of the implication is easy, of course.

  • Is it already solved for $k= 2$? (I have an idea to prove it for $k=2$ and if it works the same technique could probably be applied to other bases) – Marzio De Biasi Nov 10 at 19:50
  • $k\ge 2$ is not needed, as the statement is easy to prove for $k=1$. AFAIK it is open for every other $k$. – domotorp Nov 14 at 8:58

I think I have a proof. The proof follows from this lemma.

Lemma. For a context-free language $L$ if for infinitely many $n$ there are $n^6$ words of equal length whose first $n^2$ letters are the same and their last $n$ letters are different (pairwise), then there is a $B$ such that there are infinitely many pairs $u,v\in L$ of equal length that differ only in their last $B$ letters.

So if $u$ and $v$ represent binary numbers, then their difference will be at most $2^B$ infinitely often, which is impossible for polynomials. On the other hand, with some number theory it can be shown that the condition is satisfied for every integer valued polynomial $p$: Take any $x_1,\ldots,x_{n^6}$ for which $f(x_i)\ne f(x_j)$, and then add some sufficiently large number $N$ to each of them to obtain the desired words $f(x_i+N)$.

Proof of the lemma. Take a large enough $n$ such that there are $n^6$ words of equal length, $w_1,\ldots,w_{n^6}$, that satisfy the conditions. For each $w_i$ fix a way in which it can be generated from the context-free grammar. (Warning! I'm not an expert of this field, so I might not use the proper terms.)

Say that the application of a rule $A\to BC$ splits two letters $b$ and $c$ of the final word, if the $b$ and $c$ are both derived from $A$, but $b$ is derived from $B$, while $c$ is derived from $C$. Each rule splits at most $O(1)$ letters of $w_i$ from each other.

In any $w_i$, there will be $\Omega(n)$ consecutive letters among the first $n^2$ letters that are split from each other by some consecutive rules such that no two letters among the last $n$ letters are split from each other while applying these rules. If we write these rules collectively for letter $w_i$ as $A_i\to B_i^1B_i^2\ldots B_i^n$, then no letter from the last $n$ letters is derived from $B_i^j$ for $j<n$, and $B_i^1B_i^2\ldots B_i^{n-1}$ are all converted into some part of the first $n^2$ letters. We can apply the pumping lemma to the rule $A_i\to B_i^1B_i^2\ldots B_i^n$ if $n$ is large enough.

There are only $\binom{n^2}2$ choices for the interval of $\Omega(n)$ letters, $O(n)$ options about what the pumping lemma gives (as it has $O(1)$ length), so by the pigeonhole principle there will be two words for which these are all the same. But then after pumping we can obtain an arbitrarily long common initial part for these two words, while we know that they'll differ only in their last $n$ bits.

This is a sketch of the proof for $k=2$ and $L = \{[n^2]_2 \mid n \geq 1\}$; where $[n^2]_2$ is the binary representation of $n^2$. For better clarity we place the least significant bit of the binary strings on the left, e.g. $[4^2]_2 = 00001$.

The core idea is to assume that $L$ is context free, and then try to "simplify" it intersecting it with a simple regular language $R$; the new language $L \cap R$ is still context free and it still should contain binary representations of squares; then we apply the pumping lemma for CF languages in order to get a binary string that is not a representation of a square.

Intersecting $L$ with regular words that only contains a small finite number of $1$ digits isn't promising. It turns out that up to four $1$ digits $(R = \{ 0^*1 \}, \{ 0^*10^*1 \}, \{ 0^*10^*10^*1 \}, \{0^*10^*10^*10^*1\} )$ we get a CF language; and with five $1$ digits we get an apparently difficult number theory problem.

The promising approach is to intersect $L$ with $R = 1\,0^+\,1^+\,0^+\,1$; that is equivalent to restrict $L$ to the squares:

$$n^2 = 2^0 + 2^a((2^b - 1) + 2^{b+c}), 1<a,b,c$$

(informally odd squares whose binary representation contains all $0$s except a sequence of $1$s in the middle).

    n        n^2  n                  n^2
   39       1521  111..1             1...11111.1
  143      20449  1111...1           1....1111111..1
  543     294849  11111....1         1.....111111111...1
 2111    4456321  111111.....1       1......11111111111....1
 8319   69205761  1111111......1     1.......1111111111111.....1
33023 1090518529  11111111.......1   1........111111111111111......1
                  LSB          MSB   LSB                         MSB

With some efforts, we can prove the following:

Theorem: the number $2^0 + 2^a((2^b - 1) + 2^{b+c});\quad 0<c, 3<a<b$ is a square if and only if

$$b = 2a-3, c = a - 3 $$

(the proof is quite long, I'll publish it on my blog)

At this point, we can easily prove that $L \cap R$ is not context free using the pumping lemma (we can pump at most two "segments" of the $100..0011...1100.001$ string). So also $L$ is not context free.

Probably the same technique can be applied to any base $k$.

  • 1
    The result for $(n^2)$ in base 2 has been known for a long time. The challenge is to make a construction like this work for every polynomial that maps integers to integers, and for every base. – Jeffrey Shallit yesterday
  • 1
    We are so similar, I've also spent my last couple of days thinking about this problem, though I've taken a completely different approach. – domotorp 22 hours ago

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.