<p>Let <span class="math-container">$k &gt; 0$</span> and define an alphabet <span class="math-container">$\Sigma_k = \{ 2^0, 2^1, \ldots, 2^k \}$</span>.  Define:</p>
<p><span class="math-container">$$P_k = \{ a_1a_2\cdots a_t \in \Sigma_k^* \mid \sum_i a_i = 2^k \}.$$</span></p>
<p>This is a finite language.</p>
<p><strong>Question:</strong>  Is it true that any context-free grammar for <span class="math-container">$P_k$</span> is of size at least <span class="math-container">$2^k$</span>?</p>
<p><strong>Grammars for <span class="math-container">$P_k$</span>.</strong>  The most natural grammar, to me, has <span class="math-container">$2^k$</span> nonterminals and total size about <span class="math-container">$2^{2k}$</span>:
<span class="math-container">\begin{array}{ccl}
A_{2^k} &amp; \to &amp; 2^k \mid A_{2^k-1}A_1 \mid A_{2^k-2}A_2 \mid \cdots\\
&amp;{\vdots}\\
A_{27} &amp; \to &amp;  A_{26}A_1 \mid A_{25}A_2 \mid \cdots\\
&amp;\vdots \\
A_{16} &amp; \to &amp; 2^4 \mid A_{15}A_1 \mid A_{14}A_2 \mid \cdots\\
&amp;\vdots
\end{array}</span></p>
<p><a href="https://cstheory.stackexchange.com/users/6959/emil-je%C5%99%C3%A1bek">Emil Jeřábek</a> <a href="https://cstheory.stackexchange.com/questions/51718/smallest-context-free-grammar-for-powers-of-two-summing-to-2k#comment114458_51718">proposes</a> the regular grammar in which <span class="math-container">$A_i$</span> maps to <span class="math-container">$2^jA_{i - 2^j}$</span> for all <span class="math-container">$i, j$</span>.  As he notes, this still has <span class="math-container">$2^k$</span> nonterminals, but only <span class="math-container">$2^kk$</span> rules.</p>
<p><strong>Context:</strong>  This is doable with a size-<span class="math-container">$k$</span> one-counter automaton with binary updates, I'm interested in the comparative descriptional complexity of these models.</p>

CC BY-SA 4.0
2022-07-19T21:34:23.600Z
You can simplify the RHS to $A_i\to\ldots\mid2^jA_{i-2^j}\mid\dots$. This has the same number of nonterminals, but total size about $2^kk$, and as a bonus, it is a regular grammar.
Emil Jeřábek
CC BY-SA 4.0
2022-07-19T23:06:11.063Z
Thanks @EmilJeřábek!  I've added your grammar to the question directly.
Michaël Cadilhac
CC BY-SA 4.0
2022-07-20T13:26:02.500Z
Do you really need a $2^k$ lower bound or would a $2^{\Omega(k)}$ be good enough for your purposes?
holf
CC BY-SA 4.0
2022-07-20T14:11:57.623Z
@holf Let's say I'd offer a good beer for a $2^k$ lower bound, but only a bottle of sparkling water for a $2^{\Omega(k)}$ one.  What do you have in mind?
Michaël Cadilhac
CC BY-SA 4.0
2022-07-20T16:27:32.713Z
If $G$ recognizes $P_k$ and is in Chomsky NF, then you can show that there exists $v_1,\dots,v_p$ such that: $p \leq |G|$, $2^k/3 \leq v_i \leq (2/3)2^k$ and for every $w \in P_k$ of size at least $2$, $w$ has a sub-factor of *weight* exactly $v_i$ for some $i$ (*weight* of a word: sum of its letters).   Given $v$ in $[2^k/3; (2/3)2^k]$, let $L_v$ be the words having a subfactor of weight $v$. Now I **conjecture** $|P_k \cap L_v| < 2^{-\Omega(k)}|P_k|$. It would imply $p > 2^{\Omega(k)}$ hence $|G|$ also. Fixing a heavy subfactor seems to miss a lot of words in $P_k$ but I may be wrong.
holf
CC BY-SA 4.0
2022-08-19T15:17:23.020Z
@MichaëlCadilhac Hi, sorry but I am an outsider and needed to look up the definitions. What does "size" mean? Is it number of nonterminals plus number of rules, or do the lengths of the rules matter as well? Also, do you conjecture that one needs at least $2^k$ nonterminals?
mathworker21
CC BY-SA 4.0
2022-08-30T18:13:01.440Z
@mathworker21 The "size" is the bit-length of any reasonable encoding; it should, in any case, be lower-bounded by the number of rules.  I do conjecture you need $2^k$ nonterminals, one for each possible intermediate value.
Michaël Cadilhac
CC BY-SA 4.0
2022-11-04T21:56:45.170Z
At [Autobóz 2022](https://autoboz.org/home-22), Michał Pilipczuk and Michał Skrzypczak came up with a 2^(k/2) lower bound on the number of nonterminals. I don't remember the proof, but @MichaëlCadilhac was there.
Lê Thành Dũng 'Tito' Nguyễn
<context-free><grammars>
Smallest context-free grammar for powers of two summing to $2^k$
Michaël Cadilhac
# Smallest context-free grammar for powers of two summing to $2^k$

(Asked by: username_0 on 2022-07-19)

Let $k > 0$ and define an alphabet $\Sigma\_k = \{ 2^0, 2^1, \ldots, 2^k \}$. Define:

$$P\_k = \{ a\_1a\_2\cdots a\_t \in \Sigma\_k^\* \mid \sum\_i a\_i = 2^k \}.$$

This is a finite language.

**Question:** Is it true that any context-free grammar for $P\_k$ is of size at least $2^k$?

**Grammars for $P\_k$.** The most natural grammar, to me, has $2^k$ nonterminals and total size about $2^{2k}$:
\begin{array}{ccl}
A\_{2^k} & \to & 2^k \mid A\_{2^k-1}A\_1 \mid A\_{2^k-2}A\_2 \mid \cdots\\
&{\vdots}\\
A\_{27} & \to & A\_{26}A\_1 \mid A\_{25}A\_2 \mid \cdots\\
&\vdots \\
A\_{16} & \to & 2^4 \mid A\_{15}A\_1 \mid A\_{14}A\_2 \mid \cdots\\
&\vdots
\end{array}

[Emil Jeřábek](https://cstheory.stackexchange.com/users/6959/emil-je%C5%99%C3%A1bek) [proposes](https://cstheory.stackexchange.com/questions/51718/smallest-context-free-grammar-for-powers-of-two-summing-to-2k#comment114458_51718) the regular grammar in which $A\_i$ maps to $2^jA\_{i - 2^j}$ for all $i, j$. As he notes, this still has $2^k$ nonterminals, but only $2^kk$ rules.

**Context:** This is doable with a size-$k$ one-counter automaton with binary updates, I'm interested in the comparative descriptional complexity of these models.

**Tags:** context-free, grammars
> **Comments:**
> **username_1**: You can simplify the RHS to $A_i\to\ldots\mid2^jA_{i-2^j}\mid\dots$. This has the same number of nonterminals, but total size about $2^kk$, and as a bonus, it is a regular grammar.  
> **username_0**: Thanks @EmilJeřábek!  I've added your grammar to the question directly.  
> **username_2**: Do you really need a $2^k$ lower bound or would a $2^{\Omega(k)}$ be good enough for your purposes?  
> **username_0**: @holf Let's say I'd offer a good beer for a $2^k$ lower bound, but only a bottle of sparkling water for a $2^{\Omega(k)}$ one.  What do you have in mind?  
> **username_2**: If $G$ recognizes $P_k$ and is in Chomsky NF, then you can show that there exists $v_1,\dots,v_p$ such that: $p \leq |G|$, $2^k/3 \leq v_i \leq (2/3)2^k$ and for every $w \in P_k$ of size at least $2$, $w$ has a sub-factor of *weight* exactly $v_i$ for some $i$ (*weight* of a word: sum of its letters).   Given $v$ in $[2^k/3; (2/3)2^k]$, let $L_v$ be the words having a subfactor of weight $v$. Now I **conjecture** $|P_k \cap L_v| < 2^{-\Omega(k)}|P_k|$. It would imply $p > 2^{\Omega(k)}$ hence $|G|$ also. Fixing a heavy subfactor seems to miss a lot of words in $P_k$ but I may be wrong.  
> **username_3**: @MichaëlCadilhac Hi, sorry but I am an outsider and needed to look up the definitions. What does "size" mean? Is it number of nonterminals plus number of rules, or do the lengths of the rules matter as well? Also, do you conjecture that one needs at least $2^k$ nonterminals?  
> **username_0**: @mathworker21 The "size" is the bit-length of any reasonable encoding; it should, in any case, be lower-bounded by the number of rules.  I do conjecture you need $2^k$ nonterminals, one for each possible intermediate value.  
> **username_4**: At [Autobóz 2022](https://autoboz.org/home-22), Michał Pilipczuk and Michał Skrzypczak came up with a 2^(k/2) lower bound on the number of nonterminals. I don't remember the proof, but @MichaëlCadilhac was there.  

---

## 0 answers

