Base-k-Darstellungen der Co-Domäne eines Polynoms - ist es kontextfrei?

14

In Kapitel 4 von Jeffrey Shallits A Second Course in Automata Theory wird das folgende Problem als offen aufgeführt:

Sei ein Polynom mit rationalen Koeffizienten, so dass für alle . Beweisen oder zu widerlegen , dass die Sprache der basen k Darstellungen aller ganzen Zahlen in ist kontextfrei , wenn und nur wenn der Grad der ist .p(n)p(n)p(n)Np(n)NnNnN{p(n)n0}{p(n)n0}pp11

Wie ist der aktuelle Stand (Stand Oktober 2018)? Ist es bewiesen? Was ist mit einigen Sonderfällen?

DG_
quelle
1
Wenn (unäre Darstellung) ist, dann ist auch das einfachste nicht kontextfrei (die bekannte Nicht-CF-Sprache )k=1k=1p(n)=n2p(n)=n2L={1n2}L={1n2}
Marzio De Biasi
@MarzioDeBiasi Die sogenannte unäre Darstellung ist nicht Basis- . Die einzige in der tatsächlichen Basis Ganzzahl wäre . 111100
Emil Jeřábek unterstützt Monica
1
@ EmilJeřábek: Ich denke, dass base-1 in vielen Zusammenhängen ein Alias ​​für "unäre Repräsentation" ist .
Marzio De Biasi

Antworten:

10

Natürlich ist hier k 2k2 .

Es gab einmal ein Manuskript von Horváth, das behauptete, das Problem zu lösen, aber es war an mehreren Stellen unklar und meines Wissens wurde es nie veröffentlicht.

Soweit ich weiß, ist das Problem noch offen. Eine Richtung der Implikation ist natürlich einfach.

Jeffrey Shallit
quelle
Ist es schon für k = 2 gelöst k=2? (Ich habe die Idee, es für k = 2 zu beweisen, k=2und wenn es funktioniert, könnte die gleiche Technik wahrscheinlich auf andere Basen angewendet werden)
Marzio De Biasi
Ich würde mich sehr über ein Feedback von Ihnen zu meiner Antwort freuen.
Domotorp
Ich kann Ihre behauptete Lösung leider nicht verstehen.
Jeffrey Shallit
Ich habe eine andere Antwort mit viel mehr Details gepostet. Die ganze Aussage ist ziemlich komplex, deshalb habe ich einige einfachere Lemmas hinzugefügt, die die Hauptidee haben, hoffentlich macht das die ganze Sache glaubwürdiger.
Domotorp
3

Dies ist eine Skizze des Beweises für k = 2k=2 und L = { [ n 2 ] 2n 1 }L={[n2]2n1} ; wobei [ n 2 ] 2[n2]2 die binäre Darstellung von n 2 istn2 . Zur besseren Übersicht platzieren wir das niedrigstwertige Bit der Binärzeichenfolgen links, z. B. [ 4 2 ] 2 = 00001[42]2=00001 .

Die Kernidee ist anzunehmen, dass LL kontextfrei ist, und dann zu "vereinfachen", es mit einer einfachen regulären Sprache R zuR schneiden ; die neue Sprache L RLR ist immer noch kontextfrei und sollte immer noch binäre Darstellungen von Quadraten enthalten. dann wenden wir das Pump-Lemma für CF-Sprachen an, um eine Binärzeichenfolge zu erhalten, die keine Darstellung eines Quadrats ist.

Eine Überschneidung von LL mit regulären Wörtern, die nur eine kleine endliche Zahl von 11 Ziffern enthalten, ist nicht vielversprechend. Es stellt sich heraus , dass bis zu vier 11 - stellig ( R = { 0 * 1 } , { 0 * 10 * 1 } , { 0 * 10 * 10 * 1 } , { 0 * 10 * 10 * 10 * 1 } )(R={01},{0101},{010101},{01010101}) erhalten wir eine CF-Sprache; und mit fünf 11 Ziffern erhalten wir ein scheinbar schwieriges Problem der Zahlentheorie.

Der vielversprechende Ansatz besteht darin, LL mit R = 1 zu schneiden0 +1 +0 +1R=10+1+0+1 ; das ist äquivalent, um LL auf die Quadratezu beschränken:

n 2 = 2 0 + 2 a ( ( 2 b - 1 ) + 2 b + c ) , 1 < a , b , c

n2=20+2a((2b1)+2b+c),1<a,b,c

(informell ungeradee Quadrate , deren binäre Darstellung enthält all 00 s mit Ausnahme einer Sequenz von 11 s in der Mitte).

    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

Mit einigem Aufwand können wir folgendes beweisen:

Satz: die Zahl 2 0 + 2 a ( ( 2 b - 1 ) + 2 b + c ) ;0 < c , 3 < a < b20+2a((2b1)+2b+c);0<c,3<a<b ist genau dann ein Quadrat, wenn

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

b=2a3,c=a3

(Der Beweis ist ziemlich lang, ich werde ihn auf meinem Blog veröffentlichen.)

An diesem Punkt können wir leicht beweisen , dass L RLR frei nicht Kontext ist das Pumpen Lemma mit (wir können höchstens zwei „Segmente“ der Pumpe 100..0011 ... 1100,001100..0011...1100.001 string). Also ist auch LL nicht kontextfrei.

Wahrscheinlich kann dieselbe Technik auf jede Basis kk angewendet werden .

Marzio De Biasi
quelle
3
Das Ergebnis für ( n 2 ) in Base 2 ist seit langem bekannt. Die Herausforderung besteht darin, eine solche Konstruktion für jedes Polynom, das Ganzzahlen auf Ganzzahlen abbildet, und für jede Basis zu erstellen. (n2)
Jeffrey Shallit
1
Wir sind uns so ähnlich, dass ich in den letzten Tagen über dieses Problem nachgedacht habe, obwohl ich einen völlig anderen Ansatz gewählt habe.
Domotorp
3

Ich glaube ich habe einen Beweis. Der Beweis folgt aus diesem Lemma.

Lemma. Für eine kontextfreie Sprache LL gibt es für unendlich viele n nn 6n6 Wörter gleicher Länge, deren erste n 2n2 Buchstaben gleich sind und deren letzte nn Buchstaben unterschiedlich sind (paarweise), dann gibt es ein B,B so dass es unendlich viele gibt Paare u , v Lu,vL gleicher Länge, die sich nur in ihren letzten B-B Buchstaben unterscheiden.

Wenn also uu und vv Binärzahlen darstellen, wird ihre Differenz höchstens unendlich oft 2 B2B betragen, was für Polynome unmöglich ist. Andererseits kann mit einer gewissen Zahlentheorie gezeigt werden, dass die Bedingung für jedes ganzzahlige Polynom pp erfüllt ist : Nehmen Sie x 1 , , x n 6,x1,,xn6 für das f ( x i ) f ( x j )f(xi)f(xj) und addieren Sie dann zu jedem von ihnen eine ausreichend große Zahl NN , um die gewünschten Wörter f ( xi + N )f(xi+N).

Proof of the lemma. Take a large enough nn such that there are n6n6 words of equal length, w1,,wn6w1,,wn6, that satisfy the conditions. For each wiwi 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 ABCABC splits two letters bb and cc of the final word, if the bb and cc are both derived from AA, but bb is derived from BB, while cc is derived from CC. Each rule splits at most O(1)O(1) letters of wiwi from each other.

In any wiwi, there will be Ω(n)Ω(n) consecutive letters among the first n2n2 letters that are split from each other by some consecutive rules such that no two letters among the last nn letters are split from each other while applying these rules. If we write these rules collectively for letter wiwi as AiB1iB2iBniAiB1iB2iBni, then no letter from the last nn letters is derived from BjiBji for j<nj<n, and B1iB2iBn1iB1iB2iBn1i are all converted into some part of the first n2n2 letters. We can apply the pumping lemma to the rule AiB1iB2iBniAiB1iB2iBni if nn is large enough.

There are only (n22)(n22) choices for the interval of Ω(n)Ω(n) letters, O(n)O(n) options about what the pumping lemma gives (as it has O(1)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 nn bits.

domotorp
quelle
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.

Twin Pumping Lemma. For every context-free language LL there is a pp such that from any pp words s1,,spLs1,,spL we can select two, ss and ss, that can be written as s=uvwxys=uvwxy and s=uvwxys=uvwxy such that 1|vx|p1|vx|p, 1|vx|p1|vx|p and every word ˉuˉv1ˉvnˉwˉxnˉx1ˉyLu¯v¯1v¯nw¯x¯nx¯1y¯L, where ˉww¯ can be either ww or ww, and similarly, ˉviv¯i can be either vv or vv and ˉxix¯i can be either xx or xx, but only such that ˉvi=vv¯i=v if and only if ˉxi=xx¯i=x (thus ˉvi=vv¯i=v if and only if ˉxi=xx¯i=x), and ˉu=uu¯=u if and only if ˉy=yy¯=y and ˉu=uu¯=u if and only if ˉy=yy¯=y. Moreover, if instead of pp, we are given p(n+44)p(n+44) words of length nn, we can additionally suppose for the selected two words that |u|=|u||u|=|u|, |v|=|v||v|=|v|, |w|=|w||w|=|w|, |x|=|x||x|=|x| and |y|=|y||y|=|y|.

This statement can be proved essentially the same way as the pumping lemma, we just need to pick some ss and ss 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 (n+44) 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 sL can be written as s=uv1vkwxkx1y such that i 1|vixi|p and for every sequence (ij)mj=1 the word uvi1vimwximxi1yL.

Note that the indices ij 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(k1)+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 pk positions in any word sL, it can be written as s=uv1vkwxkx1y such that i 1 '# of marks in vixi'pk and for every sequence (ij)mj=1 the word uvi1vimwximxi1yL.

Unfortunately, in our application pk would be too large, so we need to weaken the conclusion to allow non-nested vi-xi 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, marking any at least pk positions in any word sL, it can be written either as

case (i): s=uv1vkwxkx1y, or as

case (ii): s=uv1w1x1vwxy,

such that i 1 '# of marks in vixi'pk and for every sequence (ij)mj=1,

in case (i) the word uvi1vimwximxi1yL, and

in case (ii) the word uvi11w1xi11viwxiyL.

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 leaves that correspond to a marked position. We look at the nodes where two marked letters split. There are at least Ω(pk) such nodes. By the pigeonhole principle, at least Ω(pk) correspond to the same non-terminal. Using Dilworth, Ω(pk) of them are in a chain or Ω(p) 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, marking the same at least pk positions in Nmax(pn2k+2,pn3+1) words s1,,sNL, each of length n, there are two words, s and s, that can be written as s=uv1vkwxkx1y and s=uv1vkwxkx1y OR as s=uv1w1x1vwxy and s=uv1w1x1vwxy such that the respective lengths of the subwords are all the same, i.e., |u|=|u|, |vi|=|vi|, etc., and i vixi contains a mark, and for every sequence (ij)mj=1 the word ˉuˉvi1ˉvimˉwˉximˉxi1ˉyL OR ˉuˉvi11ˉw1ˉxi11ˉviˉwˉxiˉyL, respectively, where ˉz stands for z or z, i.e., we can freely mix the intermediate subwords from s and s, but only such that ˉu=u if and only if ˉy=y etc.

Proof sketch of Super Lemma: Apply the Dilworth Ogden's Lemma for each si. There are (n+2k+22k+2) and (n+3+13+1) possible options, respectively, where the boundaries between the subwords of si 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/ 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=pkn2 words s1,,sNL, each of length n, there are two words, s and s, that can be written either as s=uv1vkwxkx1y and s=uv1vkwxkx1y such that either

case (i): i<k such that |xi|=|xi|=0, |uv1vi1|=|uv1vi1|, and |vi|=|vi| (i.e., the two latter conditions mean that the position of vi is the same as the position of vi), OR

case (ii): i<k |xi|1, |xi|1, |uv1vk1|=|uv1vk1| and |vkwxk|=|vkwxk| (i.e., these two conditions mean that the position of vkwxk is the same as the position of vkwxk),

and (for both cases) i vixi contains a mark, and for every sequence (ij)mj=1 the word ˉuˉvi1ˉvimˉwˉximˉxi1ˉyL, where ˉz stands for z or z, i.e., we can freely mix the intermediate subwords from s and s, but only such that ˉu=u if and only if ˉy=y etc., OR

case (iii): s and s can be written as s=uv1w1x1v2w2x2y and s=uv1w1x1v2w2x2y such that |u|=|u| and |v1w1x1|=|v1w1x1|, and i vixi contains a mark, and uvh1w1xh1v2w2x2yL and uvh1w1xh1v2w2x2yL.

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

Corollary. If for every p there are t and n with np(t+1)+t such that there are N=n3 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 si=sbegismidisendi such that |sbegi|=p(t+1), |smidi|=np(t+1)t, |sendi|=t, and ij sbegi=sbegj and sendisendj), then there is a B such that there are infinitely many pairs of words ahbhL 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=n3p(t+1)n2, marking the first p(t+1) letters (that are the same in every word) to obtain s=uv1vt+1wxt+1x1y and s=uv1vt+1wxt+1x1y OR s=uv1w1x1v2w2x2y and s=uv1w1x1v2w2x2y.

If we are in case (i) of the Special Lemma, i.e., there is an i such that |xi|=|xi|=0, |uv1vi1|=|uv1vi1|, and |vi|=|vi|, then uv1vi1=uv1vi1 and vi=vi also hold, as vi+1wxi+1 needs to contain a marked letter, thus the subwords preceding vi+1 consist of only marked letters, and these are the same in s and s. We can take the words ah=uv1vhivtwxtx1y and bh=uv1vhivi+1vtwxtx1y to obtain the desired pairs; since these words end the same way as s and s, ahbh and they differ only in their last bounded many letters.

If we are in case (ii) of the Special Lemma, i.e., i<k |xi|1, |xi|1, |uv1vt|=|uv1vt| and |vt+1wxt+1|=|vt+1wxt+1|, then uv1vt=uv1vt also holds, similarly as in the previous case. Now we can take ah=uv1vtvht+1wxht+1xtx1y and bh=uv1vtvht+1wxht+1xtx1y; since |xtx1y|=|xtx1y|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=uv1w1x1v2w2x2y and s=uv1w1x1v2w2x2y such that |u|=|u| and |v1w1x1|=|v1w1x1|, then u=u and v1w1x1=v1w1x1 also hold, similarly as in the previous cases. Now we can take ah=uvh1w1xh1v2w2x2yL and bh=uvh1w1xh1v2w2x2yL; since v2 contains a marked letter, |v2w2x2y|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=p1 and n=Cp for some large enough C=C(f). The plan is to take some numbers x1,,x2N (where N=2n3) for which f(xi)f(xj), and then add some sufficiently large number z to each of them to obtain the desired words si=f(xi+z). If the degree of f is d, then at most d numbers can take the same value, thus we can select x1,,x2N from the first 2dN numbers, which means that they have log(dn) digits. In this case f(xi)=O((dN)d), thus each f(xi) will have at most dlogN+O(1)=O(logn) digits. If we pick z to be an n/d digit number, then f(z) will have n digits, and for each f(xi+z) only the last O(logn) digits can differ. The f(xi+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 si.

From the conclusion of the Corollary we obtain infinitely many pairs of numbers ah and bh, such that |ahbh|2B, which is clearly impossible for polynomials.

domotorp
quelle