<p>Of course <span class="math-container">$k \geq 2$</span> here.</p>

<p>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.</p>

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

CC BY-SA 4.0
2018-11-10T19:50:01.477Z
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
CC BY-SA 4.0
2018-12-06T12:22:20.593Z
I would be very happy to hear any feedback from you about my answer.
domotorp
CC BY-SA 4.0
2018-12-07T00:04:28.223Z
I can't understand your claimed solution, sorry.
Jeffrey Shallit
CC BY-SA 4.0
2018-12-15T21:44:23.077Z
I've posted another answer with a lot more detail; the full statement is quite complex, so I've added some simpler lemmas before it that have the main idea, hopefully that makes the whole thing more believable.
domotorp
CC BY-SA 4.0
2018-11-09T20:03:40.307Z
2018-11-09T21:31:15.880Z
2018-11-09T21:31:15.880Z
Jeffrey Shallit
<p>I think I have a proof. The proof follows from this lemma.</p>

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

<p>So if <span class="math-container">$u$</span> and <span class="math-container">$v$</span> represent binary numbers, then their difference will be at most <span class="math-container">$2^B$</span> 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 <span class="math-container">$p$</span>: Take any <span class="math-container">$x_1,\ldots,x_{n^6}$</span> for which <span class="math-container">$f(x_i)\ne f(x_j)$</span>, and then add some sufficiently large number <span class="math-container">$N$</span> to each of them to obtain the desired words <span class="math-container">$f(x_i+N)$</span>.</p>

<p>Proof of the lemma. Take a large enough <span class="math-container">$n$</span> such that there are <span class="math-container">$n^6$</span> words of equal length, <span class="math-container">$w_1,\ldots,w_{n^6}$</span>, that satisfy the conditions.
For each <span class="math-container">$w_i$</span> 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.)</p>

<p>Say that the application of a rule <span class="math-container">$A\to BC$</span> <em>splits</em> two letters <span class="math-container">$b$</span> and <span class="math-container">$c$</span> of the final word, if the <span class="math-container">$b$</span> and <span class="math-container">$c$</span> are both derived from <span class="math-container">$A$</span>, but <span class="math-container">$b$</span> is derived from <span class="math-container">$B$</span>, while <span class="math-container">$c$</span> is derived from <span class="math-container">$C$</span>.
Each rule splits at most <span class="math-container">$O(1)$</span> letters of <span class="math-container">$w_i$</span> from each other.</p>

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

<p>There are only <span class="math-container">$\binom{n^2}2$</span> choices for the interval of <span class="math-container">$\Omega(n)$</span> letters, <span class="math-container">$O(n)$</span> options about what the pumping lemma gives (as it has <span class="math-container">$O(1)$</span> 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 <span class="math-container">$n$</span> bits.</p>

CC BY-SA 4.0
2018-11-18T21:27:13.277Z
2018-12-14T22:48:49.503Z
2018-12-14T22:48:49.503Z
domotorp
<p>This is a sketch of the proof for <span class="math-container">$k=2$</span> and <span class="math-container">$L = \{[n^2]_2 \mid n \geq 1\}$</span>; where <span class="math-container">$[n^2]_2$</span> is the binary representation of <span class="math-container">$n^2$</span>. For better clarity we place the least significant bit of the binary strings on the left, e.g. <span class="math-container">$[4^2]_2 = 00001$</span>.</p>

<p>The core idea is to assume that <span class="math-container">$L$</span> is context free, and then try to "simplify" it intersecting it with a simple regular language <span class="math-container">$R$</span>; the new language <span class="math-container">$L \cap R$</span> 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.</p>

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

<p>The promising approach is to intersect <span class="math-container">$L$</span> with <span class="math-container">$R = 1\,0^+\,1^+\,0^+\,1$</span>; that is equivalent to restrict <span class="math-container">$L$</span> to the squares:</p>

<p><span class="math-container">$$n^2 = 2^0 + 2^a((2^b - 1) + 2^{b+c}), 1&lt;a,b,c$$</span></p>

<p>(informally odd squares whose binary representation contains all <span class="math-container">$0$</span>s except a sequence of <span class="math-container">$1$</span>s in the middle).</p>

<pre><code>    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
</code></pre>

<p>With some efforts, we can prove the following:</p>

<p><strong>Theorem:</strong> the number 
<span class="math-container">$2^0 + 2^a((2^b - 1) + 2^{b+c});\quad 0&lt;c, 3&lt;a&lt;b$</span> is a square if and only if </p>

<p><span class="math-container">$$b = 2a-3, c = a - 3 $$</span>  </p>

<p><em>(the proof is quite long, I'll publish it on my blog)</em></p>

<p>At this point, we can easily prove that <span class="math-container">$L \cap R$</span> is not context free using the pumping lemma (we can pump at most two "segments" of the <span class="math-container">$100..0011...1100.001$</span> string). So also <span class="math-container">$L$</span> is not context free.</p>

<p>Probably the same technique can be applied to any base <span class="math-container">$k$</span>.</p>

CC BY-SA 4.0
2018-11-18T10:07:28.263Z
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
CC BY-SA 4.0
2018-11-18T21:28:18.150Z
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
CC BY-SA 4.0
2018-11-17T21:25:25.770Z
2018-11-17T21:31:27.083Z
2018-11-17T21:31:27.083Z
Marzio De Biasi
<p><strong>Note.</strong> This is a much more detailed version of my other answer, as that didn't seem to be comprehensible enough. I've tried to convert it to resemble more standard pumping lemmas, but the full proof got way to complex. I recommend to read the statement of the first two lemmas to understand the main idea, then the statement of the Corollary, and finally the end, where I prove why the Corollary implies the answer to the question.</p>

<p>The proof is based on a generalization of the pumping lemma. The lemma that we need is quite elaborate, so instead of stating it right away, I start with some easier generalizations, eventually building up to more complicated ones.
As I've later learned, this is very similar to the so-called <a href="https://epubs.siam.org/doi/10.1137/0214031" rel="nofollow noreferrer">interchange lemma</a>.</p>

<p><strong>Twin Pumping Lemma.</strong> For every context-free language <span class="math-container">$L$</span> there is a <span class="math-container">$p$</span> such that from any <span class="math-container">$p$</span> words <span class="math-container">$s_1,\ldots,s_p\in L$</span> we can select two, <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, that can be written as <span class="math-container">$s=uvwxy$</span> and <span class="math-container">$s'=u'v'w'x'y'$</span> such that <span class="math-container">$1\le |vx|\le p$</span>, <span class="math-container">$1\le |v'x'|\le p$</span> and every word <span class="math-container">$\bar u\bar v_1\ldots \bar v_n \bar w\bar x_n \ldots \bar x_1 \bar y\in L$</span>, where <span class="math-container">$\bar w$</span> can be either <span class="math-container">$w$</span> or <span class="math-container">$w'$</span>, and similarly, <span class="math-container">$\bar v_i$</span> can be either <span class="math-container">$v$</span> or <span class="math-container">$v'$</span> and <span class="math-container">$\bar x_i$</span> can be either <span class="math-container">$x$</span> or <span class="math-container">$x'$</span>, but only such that <span class="math-container">$\bar v_i=v$</span> if and only if <span class="math-container">$\bar x_i=x$</span> (thus <span class="math-container">$\bar v_i=v'$</span> if and only if <span class="math-container">$\bar x_i=x'$</span>), and <span class="math-container">$\bar u=u$</span> if and only if <span class="math-container">$\bar y=y$</span> and <span class="math-container">$\bar u=u'$</span> if and only if <span class="math-container">$\bar y=y'$</span>.
Moreover, if instead of <span class="math-container">$p$</span>, we are given <span class="math-container">$p\binom {n+4}4$</span> words of length <span class="math-container">$n$</span>, we can additionally suppose for the selected two words that <span class="math-container">$|u|=|u'|$</span>, <span class="math-container">$|v|=|v'|$</span>, <span class="math-container">$|w|=|w'|$</span>, <span class="math-container">$|x|=|x'|$</span> and <span class="math-container">$|y|=|y'|$</span>.</p>

<p>This statement can be proved essentially the same way as the pumping lemma, we just need to pick some <span class="math-container">$s$</span> and <span class="math-container">$s'$</span> for which the same rule is pumped.
This can be done if <span class="math-container">$p$</span> is large enough since there are only a constant number of rules. In fact, we don't even need that the same rule is pumped, but only that the non-terminal symbol is the same in the pumped rule.
For the moreover part, notice that for a word of length <span class="math-container">$n$</span> there are only <span class="math-container">$\binom {n+4}4$</span> options it can be broken into five subwords, thus the statement follows from the pigeonhole principle.</p>

<p>Next we give another way of generalizing the pumping lemma (and later we'll combine the two).</p>

<p><strong>Nested Pumping Lemma.</strong> For every context-free language <span class="math-container">$L$</span> there is a <span class="math-container">$p$</span> such that for any <span class="math-container">$k$</span> any word <span class="math-container">$s\in L$</span> can be written as <span class="math-container">$s=uv_1\ldots v_kwx_k\ldots x_1y$</span> such that <span class="math-container">$\forall i~1\le |v_ix_i|\le p$</span> and for every sequence <span class="math-container">$(i_j)_{j=1}^m$</span> the word <span class="math-container">$uv_{i_1}\ldots v_{i_m}wx_{i_m}\ldots x_{i_1}y\in L$</span>.</p>

<p>Note that the indices <span class="math-container">$i_j$</span> can be arbitrary from <span class="math-container">$1$</span> to <span class="math-container">$k$</span>, the same index can occur multiple times.
The proof of the Nested Pumping Lemma is essentially the same as the original pumping lemma's, we just need to use that we obtain the same non-terminal symbol from itself <span class="math-container">$k$</span> times - this is true if we do <span class="math-container">$p(k-1)+1$</span> steps (instead of the <span class="math-container">$p$</span> from the original pumping lemma).
We can also strengthen Ogden's lemma in a similar way.</p>

<p><strong>Nested Ogden's Lemma.</strong> For every context-free language <span class="math-container">$L$</span> there is a <span class="math-container">$p$</span> such that for any <span class="math-container">$k$</span> marking any at least <span class="math-container">$p^k$</span> positions in any word <span class="math-container">$s\in L$</span>, it can be written as <span class="math-container">$s=uv_1\ldots v_kwx_k\ldots x_1y$</span> such that <span class="math-container">$\forall i~1\le $</span> '# of marks in <span class="math-container">$v_ix_i$</span>'<span class="math-container">$\le p^k$</span> and for every sequence <span class="math-container">$(i_j)_{j=1}^m$</span> the word <span class="math-container">$uv_{i_1}\ldots v_{i_m}wx_{i_m}\ldots x_{i_1}y\in L$</span>.</p>

<p>Unfortunately, in our application <span class="math-container">$p^k$</span> would be too large, so we need to weaken the conclusion to allow non-nested <span class="math-container">$v_i$</span>-<span class="math-container">$x_i$</span> pairs. Luckily, using Dilworth, the structure stays simple.</p>

<p><strong>Dilworth Ogden's Lemma.</strong> For every context-free language <span class="math-container">$L$</span> there is a <span class="math-container">$p$</span> such that for any <span class="math-container">$k,\ell$</span> marking any at least <span class="math-container">$pk\ell$</span> positions in any word <span class="math-container">$s\in L$</span>, it can be written either as</p>

<p>case (i): <span class="math-container">$s=uv_1\ldots v_kwx_k\ldots x_1y$</span>, or as</p>

<p>case (ii): <span class="math-container">$s=uv_1w_1x_1\ldots v_\ell w_\ell x_\ell y$</span>,</p>

<p>such that <span class="math-container">$\forall i~1\le $</span> '# of marks in <span class="math-container">$v_ix_i$</span>'<span class="math-container">$\le pk\ell$</span> and for every sequence <span class="math-container">$(i_j)_{j=1}^m$</span>,</p>

<p>in case (i) the word <span class="math-container">$uv_{i_1}\ldots v_{i_m}wx_{i_m}\ldots x_{i_1}y\in L$</span>, and</p>

<p>in case (ii) the word <span class="math-container">$uv_1^{i_1}w_1x_1^{i_1}\ldots v_\ell^{i_\ell}w_\ell x_\ell^{i_\ell}y\in L$</span>.</p>

<p>Proof: Take the derivation tree generating <span class="math-container">$s$</span>. Call a non-terminal <em>recurring</em> if it appears again under itself in the derivation tree. By expanding the rule set, we can suppose that all non-terminal symbols are recurring in the derivation tree. (This is to be understood that we might have eliminated their recurrence; this doesn't matter, the point is that they can be pumped.) There are at least <span class="math-container">$pk\ell$</span> leaves that correspond to a marked position. We look at the nodes where two marked letters split. There are at least <span class="math-container">$\Omega(pk\ell)$</span> such nodes. By the pigeonhole principle, at least <span class="math-container">$\Omega(pk\ell)$</span> correspond to the same non-terminal. Using Dilworth, <span class="math-container">$\Omega(\sqrt{p}k)$</span> of them are in a chain or <span class="math-container">$\Omega(\sqrt{p}\ell)$</span> are in an antichain, giving cases (i) and (ii), respectively, if <span class="math-container">$p$</span> is large enough.</p>

<p>Now we are ready to state a big combination lemma.</p>

<p><strong>Super Lemma.</strong> For every context-free language <span class="math-container">$L$</span> there is a <span class="math-container">$p$</span> such that for any <span class="math-container">$k,\ell$</span> marking the same at least <span class="math-container">$pk\ell$</span> positions in <span class="math-container">$N\ge \max(pn^{2k+2},pn^{3\ell+1})$</span> words <span class="math-container">$s_1,\ldots,s_N\in L$</span>, each of length <span class="math-container">$n$</span>, there are two words, <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, that can be written as <span class="math-container">$s=uv_1\ldots v_kwx_k\ldots x_1y$</span> and <span class="math-container">$s'=u'v_1'\ldots v_k'w'x_k'\ldots x_1'y'$</span> OR as <span class="math-container">$s=uv_1w_1x_1\ldots v_\ell w_\ell x_\ell y$</span> and <span class="math-container">$s'=u'v_1'w_1'x_1'\ldots v_\ell'w_\ell'x_\ell'y'$</span> such that the respective lengths of the subwords are all the same, i.e., <span class="math-container">$|u|=|u'|$</span>, <span class="math-container">$|v_i|=|v_i'|$</span>, etc., and <span class="math-container">$\forall i$</span> <span class="math-container">$v_ix_i$</span> contains a mark, and for every sequence <span class="math-container">$(i_j)_{j=1}^m$</span> the word <span class="math-container">$\bar u\bar v_{i_1}\ldots \bar v_{i_m}\bar w\bar x_{i_m}\ldots \bar x_{i_1} \bar y\in L$</span> OR <span class="math-container">$\bar u\bar v_1^{i_1}\bar w_1\bar x_1^{i_1}\ldots \bar v_\ell^{i_\ell}\bar w_\ell \bar x_\ell^{i_\ell}\bar y \in L$</span>, respectively, where <span class="math-container">$\bar z$</span> stands for <span class="math-container">$z$</span> or <span class="math-container">$z'$</span>, i.e., we can freely mix the intermediate subwords from <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, but only such that <span class="math-container">$\bar u=u$</span> if and only if <span class="math-container">$\bar y=y$</span> etc.</p>

<p>Proof sketch of Super Lemma: Apply the Dilworth Ogden's Lemma for each <span class="math-container">$s_i$</span>. There are <span class="math-container">$\binom {n+2k+2}{2k+2}$</span> and <span class="math-container">$\binom {n+3\ell+1}{3\ell+1}$</span> possible options, respectively, where the boundaries between the subwords of <span class="math-container">$s_i$</span> can be. There are a constant number of non-terminals in the language, thus by the pigeonhole principle, if <span class="math-container">$p$</span> is large enough, the same non-terminal is pumped in the <span class="math-container">$k$</span>/<span class="math-container">$\ell$</span> rules for at least two words, <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, that also have the same subword boundaries.</p>

<p>Unfortunately, the number <span class="math-container">$N$</span> that comes from this lemma is too large for our application. We can, however, decrease it by demanding fewer coincidences among the subwords. Now we state the lemma that we'll use.</p>

<p><strong>Special Lemma.</strong>  For every context-free language <span class="math-container">$L$</span> there is a <span class="math-container">$p$</span> such that for any <span class="math-container">$k$</span> marking the same at least <span class="math-container">$pk$</span> positions in <span class="math-container">$N=pkn^2$</span> words <span class="math-container">$s_1,\ldots,s_N\in L$</span>, each of length <span class="math-container">$n$</span>, there are two words, <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, that can be written either as <span class="math-container">$s=uv_1\ldots v_kwx_k\ldots x_1y$</span> and <span class="math-container">$s'=u'v_1'\ldots v_k'w'x_k'\ldots x_1'y'$</span> such that either</p>

<p><strong>case (i):</strong> <span class="math-container">$\exists i&lt;k$</span> such that <span class="math-container">$|x_i|=|x_i'|=0$</span>, <span class="math-container">$|uv_1\ldots v_{i-1}|=|u'v_1'\ldots v_{i-1}'|$</span>, and <span class="math-container">$|v_i|=|v_i'|$</span> (i.e., the two latter conditions mean that the position of <span class="math-container">$v_i$</span> is the same as the position of <span class="math-container">$v_i'$</span>), OR </p>

<p><strong>case (ii):</strong> <span class="math-container">$\forall i&lt;k$</span> <span class="math-container">$|x_i|\ge 1$</span>, <span class="math-container">$|x_i'|\ge 1$</span>, <span class="math-container">$|uv_1\ldots v_{k-1}|=|u'v_1'\ldots v_{k-1}'|$</span> and <span class="math-container">$|v_kwx_k|=|v_k'w'x_k'|$</span> (i.e., these two conditions mean that the position of <span class="math-container">$v_kwx_k$</span> is the same as the position of <span class="math-container">$v_k'w'x_k'$</span>),</p>

<p>and (for both cases) <span class="math-container">$\forall i$</span> <span class="math-container">$v_ix_i$</span> contains a mark, and for every sequence <span class="math-container">$(i_j)_{j=1}^m$</span> the word <span class="math-container">$\bar u\bar v_{i_1}\ldots \bar v_{i_m}\bar w\bar x_{i_m}\ldots \bar x_{i_1}\bar y\in L$</span>, where <span class="math-container">$\bar z$</span> stands for <span class="math-container">$z$</span> or <span class="math-container">$z'$</span>, i.e., we can freely mix the intermediate subwords from <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, but only such that <span class="math-container">$\bar u=u$</span> if and only if <span class="math-container">$\bar y=y$</span> etc., OR</p>

<p><strong>case (iii):</strong> <span class="math-container">$s$</span> and <span class="math-container">$s'$</span> can be written as <span class="math-container">$s=uv_1w_1x_1v_2w_2x_2y$</span> and <span class="math-container">$s'=u'v_1'w_1'x_1'v_2'w_2'x_2'y'$</span> such that <span class="math-container">$|u|=|u'|$</span> and <span class="math-container">$|v_1w_1x_1|=|v_1'w_1'x_1'|$</span>, and <span class="math-container">$\forall i$</span> <span class="math-container">$v_ix_i$</span> contains a mark, and <span class="math-container">$uv_1^hw_1x_1^hv_2w_2x_2y\in L$</span> and <span class="math-container">$u'v_1^hw_1x_1^hv_2'w_2'x_2'y'\in L$</span>.</p>

<p>The proof only differs from the Super Lemma's that there are <span class="math-container">$k\binom n2$</span> possible options for a word in case (i), which leaves <span class="math-container">$\binom n2$</span> options for case (ii), while in case (iii) there are <span class="math-container">$\binom n2$</span> options.</p>

<p><strong>Corollary.</strong> If for every <span class="math-container">$p$</span> there are <span class="math-container">$t$</span> and <span class="math-container">$n$</span> with <span class="math-container">$n\ge p(t+1)+t$</span> such that there are <span class="math-container">$N=n^3$</span> words of length <span class="math-container">$n$</span> in a context-free language <span class="math-container">$L$</span> whose first <span class="math-container">$p(t+1)$</span> letters are the same for each word, and their last <span class="math-container">$t$</span> letters are different for each pair or words (i.e., the words look like <span class="math-container">$s_i=s_i^{beg}s_i^{mid}s_i^{end}$</span> such that <span class="math-container">$|s_i^{beg}|=p(t+1)$</span>, <span class="math-container">$|s_i^{mid}|=n-p(t+1)-t$</span>, <span class="math-container">$|s_i^{end}|=t$</span>, and <span class="math-container">$\forall i\ne j~s_i^{beg}= s_j^{beg}$</span> and <span class="math-container">$s_i^{end}\ne s_j^{end}$</span>), then there is a <span class="math-container">$B$</span> such that there are infinitely many pairs of words <span class="math-container">$a_h\ne b_h\in L$</span> of equal length that differ only in their last <span class="math-container">$B$</span> letters.</p>

<p>Proof: Take <span class="math-container">$k=t+1$</span> and apply the Special Lemma for our <span class="math-container">$N$</span> words using <span class="math-container">$N=n^3\ge p(t+1)n^2$</span>, marking the first <span class="math-container">$p(t+1)$</span> letters (that are the same in every word) to obtain <span class="math-container">$s=uv_1\ldots v_{t+1}wx_{t+1}\ldots x_1y$</span> and <span class="math-container">$s'=u'v_1'\ldots v_{t+1}'w'x_{t+1}'\ldots x_1'y'$</span> OR <span class="math-container">$s=uv_1w_1x_1v_2w_2x_2y$</span> and <span class="math-container">$s'=u'v_1'w_1'x_1'v_2'w_2'x_2'y'$</span>.</p>

<p>If we are in case (i) of the Special Lemma, i.e., there is an <span class="math-container">$i$</span> such that <span class="math-container">$|x_i|=|x_i'|=0$</span>, <span class="math-container">$|uv_1\ldots v_{i-1}|=|u'v_1'\ldots v_{i-1}'|$</span>, and <span class="math-container">$|v_i|=|v_i'|$</span>, then <span class="math-container">$uv_1\ldots v_{i-1}=u'v_1'\ldots v_{i-1}'$</span> and <span class="math-container">$v_i=v_i'$</span> also hold, as <span class="math-container">$v_{i+1}wx_{i+1}$</span> needs to contain a marked letter, thus the subwords preceding <span class="math-container">$v_{i+1}$</span> consist of only marked letters, and these are the same in <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>.
We can take the words <span class="math-container">$a_h=uv_1\ldots v_i^h\ldots v_twx_t\ldots x_1y$</span> and <span class="math-container">$b_h=uv_1\ldots v_i^hv_{i+1}'\ldots v_t'w'x_t'\ldots x_1'y'$</span> to obtain the desired pairs; since these words end the same way as <span class="math-container">$s$</span> and <span class="math-container">$s'$</span>, <span class="math-container">$a_h\ne b_h$</span> and they differ only in their last bounded many letters. </p>

<p>If we are in case (ii) of the Special Lemma, i.e., <span class="math-container">$\forall i&lt;k$</span> <span class="math-container">$|x_i|\ge 1$</span>, <span class="math-container">$|x_i'|\ge 1$</span>, <span class="math-container">$|uv_1\ldots v_t|=|u'v_1'\ldots v_t'|$</span> and <span class="math-container">$|v_{t+1}wx_{t+1}|=|v_{t+1}'w'x_{t+1}'|$</span>, then <span class="math-container">$uv_1\ldots v_t=u'v_1'\ldots v_t'$</span> also holds, similarly as in the previous case.
Now we can take <span class="math-container">$a_h=uv_1\ldots v_tv_{t+1}^{h}wx_{t+1}^{h}x_t\ldots x_1y$</span> and <span class="math-container">$b_h=uv_1\ldots v_tv_{t+1}^{h}wx_{t+1}^{h}x_t'\ldots x_1'y'$</span>; since <span class="math-container">$|x_t\ldots x_1y|=|x_t'\ldots x_1'y'|\ge t$</span>, these words certainly end differently and can differ only in their last bounded many letters.
(Note that this is the only place where we really need that we can pump one word with a subword of the other one.)</p>

<p>If we are in case (iii) of the Special Lemma, i.e., <span class="math-container">$s=uv_1w_1x_1v_2w_2x_2y$</span> and <span class="math-container">$s'=u'v_1'w_1'x_1'v_2'w_2'x_2'y'$</span> such that <span class="math-container">$|u|=|u'|$</span> and <span class="math-container">$|v_1w_1x_1|=|v_1'w_1'x_1'|$</span>, then <span class="math-container">$u=u'$</span> and <span class="math-container">$v_1w_1x_1=v_1'w_1'x_1'$</span> also hold, similarly as in the previous cases.
Now we can take <span class="math-container">$a_h=uv_1^hw_1x_1^hv_2w_2x_2y\in L$</span> and <span class="math-container">$b_h=uv_1^hw_1x_1^hv_2'w_2'x_2'y'\in L$</span>; since <span class="math-container">$v_2$</span> contains a marked letter, <span class="math-container">$|v_2w_2x_2y|\ge t$</span>, thus these words certainly end differently and can differ only in their last bounded many letters.    </p>

<p>This finishes the proof of the Corollary.
Now let's see how to prove the original question from the Corollary.</p>

<p><strong>Final proof.</strong>
First we show that the condition of the Corollary is satisfied for every integer valued polynomial <span class="math-container">$f$</span>. Set <span class="math-container">$t=p-1$</span> and <span class="math-container">$n=C^p$</span> for some large enough <span class="math-container">$C=C(f)$</span>. The plan is to take some numbers <span class="math-container">$x_1,\ldots,x_{2N}$</span> (where <span class="math-container">$N=2n^3$</span>) for which <span class="math-container">$f(x_i)\ne f(x_j)$</span>, and then add some sufficiently large number <span class="math-container">$z$</span> to each of them to obtain the desired words <span class="math-container">$s_i=f(x_i+z)$</span>. If the degree of <span class="math-container">$f$</span> is <span class="math-container">$d$</span>, then at most <span class="math-container">$d$</span> numbers can take the same value, thus we can select <span class="math-container">$x_1,\ldots,x_{2N}$</span> from the first <span class="math-container">$2dN$</span> numbers, which means that they have <span class="math-container">$\log(dn)$</span> digits. In this case <span class="math-container">$f(x_i)=O((dN)^d)$</span>, thus each <span class="math-container">$f(x_i)$</span> will have at most <span class="math-container">$d\log N + O(1)=O(\log n)$</span> digits. If we pick <span class="math-container">$z$</span> to be an <span class="math-container">$n/d$</span> digit number, then <span class="math-container">$f(z)$</span> will have <span class="math-container">$n$</span> digits, and for each <span class="math-container">$f(x_i+z)$</span> only the last <span class="math-container">$O(\log n)$</span> digits can differ. The <span class="math-container">$f(x_i+z)$</span> will all have <span class="math-container">$n$</span> or <span class="math-container">$n+1$</span> digits, thus at least half, i.e., <span class="math-container">$N$</span> of them have the same length; these will be the <span class="math-container">$s_i$</span>.</p>

<p>From the conclusion of the Corollary we obtain infinitely many pairs of numbers <span class="math-container">$a_h$</span> and <span class="math-container">$b_h$</span>, such that <span class="math-container">$|a_h-b_h|\le 2^B$</span>, which is clearly impossible for polynomials.</p>

CC BY-SA 4.0
2018-12-14T22:47:14.503Z
2019-01-02T20:29:40.020Z
2019-01-02T20:29:40.020Z
domotorp
<p>In chapter 4 of Jeffrey Shallit's <em>A Second Course in Automata Theory</em> the following problem is listed as open:</p>

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

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

CC BY-SA 4.0
2018-11-09T16:27:03.007Z
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
CC BY-SA 4.0
2018-11-19T08:07:04.037Z
@MarzioDeBiasi The so-called unary representation is not base-$1$. The only integer representable in actual base-$1$ would be $0$.
Emil Jeřábek
CC BY-SA 4.0
2018-11-20T11:25:58.440Z
@EmilJeřábek: I think that  in many contexts [base-1 is an alias of "unary representation"](https://en.wikipedia.org/wiki/Unary_numeral_system).
Marzio De Biasi
CC BY-SA 4.0
2024-03-06T20:22:58.200Z
Btw, my solution to this problem that started as my answer here appeared in a journal 3 years ago: https://doi.org/10.14736/kyb-2020-4-0722
domotorp
<fl.formal-languages><nt.number-theory><grammars>
Base-k representations of the co-domain of a polynomial - is it context-free?
DG_
# Base-k representations of the co-domain of a polynomial - is it context-free?

(Asked by: username_0 on 2018-11-08)

In chapter 4 of username_4'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?

**Tags:** fl.formal-languages, nt.number-theory, grammars

> **Comments:**
> **username_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} \}$)  
> **username_2**: @MarzioDeBiasi The so-called unary representation is not base-$1$. The only integer representable in actual base-$1$ would be $0$.  
> **username_1**: @EmilJeřábek: I think that  in many contexts [base-1 is an alias of "unary representation"](https://en.wikipedia.org/wiki/Unary_numeral_system).  
> **username_3**: Btw, my solution to this problem that started as my answer here appeared in a journal 3 years ago: https://doi.org/10.14736/kyb-2020-4-0722  

---

## 4 answers

### Answer by username_4 on 2018-11-09. Score: 10

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.

> **Comments:**
> **username_1**: 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)  
> **username_3**: I would be very happy to hear any feedback from you about my answer.  
> **username_4**: I can't understand your claimed solution, sorry.  
> **username_3**: I've posted another answer with a lot more detail; the full statement is quite complex, so I've added some simpler lemmas before it that have the main idea, hopefully that makes the whole thing more believable.  

---

### Answer by username_3 on 2018-11-18. Score: 3

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, 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.


---

### Answer by username_1 on 2018-11-17. Score: 3

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
(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 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$.

> **Comments:**
> **username_4**: 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.  
> **username_3**: 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.  

---

### Answer by username_3 on 2018-12-14. Score: 1

**Note.** This is a much more detailed version of my other answer, as that didn't seem to be comprehensible enough. I've tried to convert it to resemble more standard pumping lemmas, but the full proof got way to complex. I recommend to read the statement of the first two lemmas to understand the main idea, then the statement of the Corollary, and finally the end, where I prove why the Corollary implies the answer to the question.

The proof is based on a generalization of the pumping lemma. The lemma that we need is quite elaborate, so instead of stating it right away, I start with some easier generalizations, eventually building up to more complicated ones.
As I've later learned, this is very similar to the so-called [interchange lemma](https://epubs.siam.org/doi/10.1137/0214031).

**Twin Pumping Lemma.** For every context-free language $L$ there is a $p$ such that from any $p$ words $s\_1,\ldots,s\_p\in L$ we can select two, $s$ and $s'$, that can be written as $s=uvwxy$ and $s'=u'v'w'x'y'$ such that $1\le |vx|\le p$, $1\le |v'x'|\le p$ and every word $\bar u\bar v\_1\ldots \bar v\_n \bar w\bar x\_n \ldots \bar x\_1 \bar y\in L$, where $\bar w$ can be either $w$ or $w'$, and similarly, $\bar v\_i$ can be either $v$ or $v'$ and $\bar x\_i$ can be either $x$ or $x'$, but only such that $\bar v\_i=v$ if and only if $\bar x\_i=x$ (thus $\bar v\_i=v'$ if and only if $\bar x\_i=x'$), and $\bar u=u$ if and only if $\bar y=y$ and $\bar u=u'$ if and only if $\bar y=y'$.
Moreover, if instead of $p$, we are given $p\binom {n+4}4$ words of length $n$, we can additionally suppose for the selected two words that $|u|=|u'|$, $|v|=|v'|$, $|w|=|w'|$, $|x|=|x'|$ and $|y|=|y'|$.

This statement can be proved essentially the same way as the pumping lemma, we just need to pick some $s$ and $s'$ for which the same rule is pumped.
This can be done if $p$ is large enough since there are only a constant number of rules. In fact, we don't even need that the same rule is pumped, but only that the non-terminal symbol is the same in the pumped rule.
For the moreover part, notice that for a word of length $n$ there are only $\binom {n+4}4$ options it can be broken into five subwords, thus the statement follows from the pigeonhole principle.

Next we give another way of generalizing the pumping lemma (and later we'll combine the two).

**Nested Pumping Lemma.** For every context-free language $L$ there is a $p$ such that for any $k$ any word $s\in L$ can be written as $s=uv\_1\ldots v\_kwx\_k\ldots x\_1y$ such that $\forall i~1\le |v\_ix\_i|\le p$ and for every sequence $(i\_j)\_{j=1}^m$ the word $uv\_{i\_1}\ldots v\_{i\_m}wx\_{i\_m}\ldots x\_{i\_1}y\in L$.

Note that the indices $i\_j$ can be arbitrary from $1$ to $k$, the same index can occur multiple times.
The proof of the Nested Pumping Lemma is essentially the same as the original pumping lemma's, we just need to use that we obtain the same non-terminal symbol from itself $k$ times - this is true if we do $p(k-1)+1$ steps (instead of the $p$ from the original pumping lemma).
We can also strengthen Ogden's lemma in a similar way.

**Nested Ogden's Lemma.** For every context-free language $L$ there is a $p$ such that for any $k$ marking any at least $p^k$ positions in any word $s\in L$, it can be written as $s=uv\_1\ldots v\_kwx\_k\ldots x\_1y$ such that $\forall i~1\le $ '# of marks in $v\_ix\_i$'$\le p^k$ and for every sequence $(i\_j)\_{j=1}^m$ the word $uv\_{i\_1}\ldots v\_{i\_m}wx\_{i\_m}\ldots x\_{i\_1}y\in L$.

Unfortunately, in our application $p^k$ would be too large, so we need to weaken the conclusion to allow non-nested $v\_i$-$x\_i$ pairs. Luckily, using Dilworth, the structure stays simple.

**Dilworth Ogden's Lemma.** For every context-free language $L$ there is a $p$ such that for any $k,\ell$ marking any at least $pk\ell$ positions in any word $s\in L$, it can be written either as

case (i): $s=uv\_1\ldots v\_kwx\_k\ldots x\_1y$, or as

case (ii): $s=uv\_1w\_1x\_1\ldots v\_\ell w\_\ell x\_\ell y$,

such that $\forall i~1\le $ '# of marks in $v\_ix\_i$'$\le pk\ell$ and for every sequence $(i\_j)\_{j=1}^m$,

in case (i) the word $uv\_{i\_1}\ldots v\_{i\_m}wx\_{i\_m}\ldots x\_{i\_1}y\in L$, and

in case (ii) the word $uv\_1^{i\_1}w\_1x\_1^{i\_1}\ldots v\_\ell^{i\_\ell}w\_\ell x\_\ell^{i\_\ell}y\in L$.

Proof: Take the derivation tree generating $s$. Call a non-terminal *recurring* if it appears again under itself in the derivation tree. By expanding the rule set, we can suppose that all non-terminal symbols are recurring in the derivation tree. (This is to be understood that we might have eliminated their recurrence; this doesn't matter, the point is that they can be pumped.) There are at least $pk\ell$ leaves that correspond to a marked position. We look at the nodes where two marked letters split. There are at least $\Omega(pk\ell)$ such nodes. By the pigeonhole principle, at least $\Omega(pk\ell)$ correspond to the same non-terminal. Using Dilworth, $\Omega(\sqrt{p}k)$ of them are in a chain or $\Omega(\sqrt{p}\ell)$ are in an antichain, giving cases (i) and (ii), respectively, if $p$ is large enough.

Now we are ready to state a big combination lemma.

**Super Lemma.** For every context-free language $L$ there is a $p$ such that for any $k,\ell$ marking the same at least $pk\ell$ positions in $N\ge \max(pn^{2k+2},pn^{3\ell+1})$ words $s\_1,\ldots,s\_N\in L$, each of length $n$, there are two words, $s$ and $s'$, that can be written as $s=uv\_1\ldots v\_kwx\_k\ldots x\_1y$ and $s'=u'v\_1'\ldots v\_k'w'x\_k'\ldots x\_1'y'$ OR as $s=uv\_1w\_1x\_1\ldots v\_\ell w\_\ell x\_\ell y$ and $s'=u'v\_1'w\_1'x\_1'\ldots v\_\ell'w\_\ell'x\_\ell'y'$ such that the respective lengths of the subwords are all the same, i.e., $|u|=|u'|$, $|v\_i|=|v\_i'|$, etc., and $\forall i$ $v\_ix\_i$ contains a mark, and for every sequence $(i\_j)\_{j=1}^m$ the word $\bar u\bar v\_{i\_1}\ldots \bar v\_{i\_m}\bar w\bar x\_{i\_m}\ldots \bar x\_{i\_1} \bar y\in L$ OR $\bar u\bar v\_1^{i\_1}\bar w\_1\bar x\_1^{i\_1}\ldots \bar v\_\ell^{i\_\ell}\bar w\_\ell \bar x\_\ell^{i\_\ell}\bar y \in L$, respectively, where $\bar z$ stands for $z$ or $z'$, i.e., we can freely mix the intermediate subwords from $s$ and $s'$, but only such that $\bar u=u$ if and only if $\bar y=y$ etc.

Proof sketch of Super Lemma: Apply the Dilworth Ogden's Lemma for each $s\_i$. There are $\binom {n+2k+2}{2k+2}$ and $\binom {n+3\ell+1}{3\ell+1}$ possible options, respectively, where the boundaries between the subwords of $s\_i$ can be. There are a constant number of non-terminals in the language, thus by the pigeonhole principle, if $p$ is large enough, the same non-terminal is pumped in the $k$/$\ell$ rules for at least two words, $s$ and $s'$, that also have the same subword boundaries.

Unfortunately, the number $N$ that comes from this lemma is too large for our application. We can, however, decrease it by demanding fewer coincidences among the subwords. Now we state the lemma that we'll use.

**Special Lemma.** For every context-free language $L$ there is a $p$ such that for any $k$ marking the same at least $pk$ positions in $N=pkn^2$ words $s\_1,\ldots,s\_N\in L$, each of length $n$, there are two words, $s$ and $s'$, that can be written either as $s=uv\_1\ldots v\_kwx\_k\ldots x\_1y$ and $s'=u'v\_1'\ldots v\_k'w'x\_k'\ldots x\_1'y'$ such that either

**case (i):** $\exists i such that $|x\_i|=|x\_i'|=0$, $|uv\_1\ldots v\_{i-1}|=|u'v\_1'\ldots v\_{i-1}'|$, and $|v\_i|=|v\_i'|$ (i.e., the two latter conditions mean that the position of $v\_i$ is the same as the position of $v\_i'$), OR

**case (ii):** $\forall i $|x\_i|\ge 1$, $|x\_i'|\ge 1$, $|uv\_1\ldots v\_{k-1}|=|u'v\_1'\ldots v\_{k-1}'|$ and $|v\_kwx\_k|=|v\_k'w'x\_k'|$ (i.e., these two conditions mean that the position of $v\_kwx\_k$ is the same as the position of $v\_k'w'x\_k'$),

and (for both cases) $\forall i$ $v\_ix\_i$ contains a mark, and for every sequence $(i\_j)\_{j=1}^m$ the word $\bar u\bar v\_{i\_1}\ldots \bar v\_{i\_m}\bar w\bar x\_{i\_m}\ldots \bar x\_{i\_1}\bar y\in L$, where $\bar z$ stands for $z$ or $z'$, i.e., we can freely mix the intermediate subwords from $s$ and $s'$, but only such that $\bar u=u$ if and only if $\bar y=y$ etc., OR

**case (iii):** $s$ and $s'$ can be written as $s=uv\_1w\_1x\_1v\_2w\_2x\_2y$ and $s'=u'v\_1'w\_1'x\_1'v\_2'w\_2'x\_2'y'$ such that $|u|=|u'|$ and $|v\_1w\_1x\_1|=|v\_1'w\_1'x\_1'|$, and $\forall i$ $v\_ix\_i$ contains a mark, and $uv\_1^hw\_1x\_1^hv\_2w\_2x\_2y\in L$ and $u'v\_1^hw\_1x\_1^hv\_2'w\_2'x\_2'y'\in L$.

The proof only differs from the Super Lemma's that there are $k\binom n2$ possible options for a word in case (i), which leaves $\binom n2$ options for case (ii), while in case (iii) there are $\binom n2$ options.

**Corollary.** If for every $p$ there are $t$ and $n$ with $n\ge p(t+1)+t$ such that there are $N=n^3$ words of length $n$ in a context-free language $L$ whose first $p(t+1)$ letters are the same for each word, and their last $t$ letters are different for each pair or words (i.e., the words look like $s\_i=s\_i^{beg}s\_i^{mid}s\_i^{end}$ such that $|s\_i^{beg}|=p(t+1)$, $|s\_i^{mid}|=n-p(t+1)-t$, $|s\_i^{end}|=t$, and $\forall i\ne j~s\_i^{beg}= s\_j^{beg}$ and $s\_i^{end}\ne s\_j^{end}$), then there is a $B$ such that there are infinitely many pairs of words $a\_h\ne b\_h\in L$ of equal length that differ only in their last $B$ letters.

Proof: Take $k=t+1$ and apply the Special Lemma for our $N$ words using $N=n^3\ge p(t+1)n^2$, marking the first $p(t+1)$ letters (that are the same in every word) to obtain $s=uv\_1\ldots v\_{t+1}wx\_{t+1}\ldots x\_1y$ and $s'=u'v\_1'\ldots v\_{t+1}'w'x\_{t+1}'\ldots x\_1'y'$ OR $s=uv\_1w\_1x\_1v\_2w\_2x\_2y$ and $s'=u'v\_1'w\_1'x\_1'v\_2'w\_2'x\_2'y'$.

If we are in case (i) of the Special Lemma, i.e., there is an $i$ such that $|x\_i|=|x\_i'|=0$, $|uv\_1\ldots v\_{i-1}|=|u'v\_1'\ldots v\_{i-1}'|$, and $|v\_i|=|v\_i'|$, then $uv\_1\ldots v\_{i-1}=u'v\_1'\ldots v\_{i-1}'$ and $v\_i=v\_i'$ also hold, as $v\_{i+1}wx\_{i+1}$ needs to contain a marked letter, thus the subwords preceding $v\_{i+1}$ consist of only marked letters, and these are the same in $s$ and $s'$.
We can take the words $a\_h=uv\_1\ldots v\_i^h\ldots v\_twx\_t\ldots x\_1y$ and $b\_h=uv\_1\ldots v\_i^hv\_{i+1}'\ldots v\_t'w'x\_t'\ldots x\_1'y'$ to obtain the desired pairs; since these words end the same way as $s$ and $s'$, $a\_h\ne b\_h$ and they differ only in their last bounded many letters.

If we are in case (ii) of the Special Lemma, i.e., $\forall i $|x\_i|\ge 1$, $|x\_i'|\ge 1$, $|uv\_1\ldots v\_t|=|u'v\_1'\ldots v\_t'|$ and $|v\_{t+1}wx\_{t+1}|=|v\_{t+1}'w'x\_{t+1}'|$, then $uv\_1\ldots v\_t=u'v\_1'\ldots v\_t'$ also holds, similarly as in the previous case.
Now we can take $a\_h=uv\_1\ldots v\_tv\_{t+1}^{h}wx\_{t+1}^{h}x\_t\ldots x\_1y$ and $b\_h=uv\_1\ldots v\_tv\_{t+1}^{h}wx\_{t+1}^{h}x\_t'\ldots x\_1'y'$; since $|x\_t\ldots x\_1y|=|x\_t'\ldots x\_1'y'|\ge t$, these words certainly end differently and can differ only in their last bounded many letters.
(Note that this is the only place where we really need that we can pump one word with a subword of the other one.)

If we are in case (iii) of the Special Lemma, i.e., $s=uv\_1w\_1x\_1v\_2w\_2x\_2y$ and $s'=u'v\_1'w\_1'x\_1'v\_2'w\_2'x\_2'y'$ such that $|u|=|u'|$ and $|v\_1w\_1x\_1|=|v\_1'w\_1'x\_1'|$, then $u=u'$ and $v\_1w\_1x\_1=v\_1'w\_1'x\_1'$ also hold, similarly as in the previous cases.
Now we can take $a\_h=uv\_1^hw\_1x\_1^hv\_2w\_2x\_2y\in L$ and $b\_h=uv\_1^hw\_1x\_1^hv\_2'w\_2'x\_2'y'\in L$; since $v\_2$ contains a marked letter, $|v\_2w\_2x\_2y|\ge t$, thus these words certainly end differently and can differ only in their last bounded many letters.

This finishes the proof of the Corollary.
Now let's see how to prove the original question from the Corollary.

**Final proof.**
First we show that the condition of the Corollary is satisfied for every integer valued polynomial $f$. Set $t=p-1$ and $n=C^p$ for some large enough $C=C(f)$. The plan is to take some numbers $x\_1,\ldots,x\_{2N}$ (where $N=2n^3$) for which $f(x\_i)\ne f(x\_j)$, and then add some sufficiently large number $z$ to each of them to obtain the desired words $s\_i=f(x\_i+z)$. If the degree of $f$ is $d$, then at most $d$ numbers can take the same value, thus we can select $x\_1,\ldots,x\_{2N}$ from the first $2dN$ numbers, which means that they have $\log(dn)$ digits. In this case $f(x\_i)=O((dN)^d)$, thus each $f(x\_i)$ will have at most $d\log N + O(1)=O(\log n)$ digits. If we pick $z$ to be an $n/d$ digit number, then $f(z)$ will have $n$ digits, and for each $f(x\_i+z)$ only the last $O(\log n)$ digits can differ. The $f(x\_i+z)$ will all have $n$ or $n+1$ digits, thus at least half, i.e., $N$ of them have the same length; these will be the $s\_i$.

From the conclusion of the Corollary we obtain infinitely many pairs of numbers $a\_h$ and $b\_h$, such that $|a\_h-b\_h|\le 2^B$, which is clearly impossible for polynomials.


---

