# On particular sumset properties of permanent?

Denote $$\mathcal R_2[n]=\mathcal R[n] + \mathcal R[n]$$ to be sumset of integers in $$\mathcal R[n]$$ where $$\mathcal R[n]$$ to be set of permanents possible with permanents of $$n\times n$$ matrices with $$0/1$$ entries.

We have:

$$\mathcal R_2[1]=\mathcal R[1]+\mathcal R[1]=\{0,1\}+\{0,1\}=\{0,1,2\}\subseteq\mathcal R[2]$$

$$\mathcal R_2[2]=\mathcal R[2]+\mathcal R[2]=\{0,1,2\}+\{0,1,2\}=\{0,1,2,3,4\}\subseteq\mathcal R[3]$$

$$\mathcal R_2[3]=\mathcal R[3]+\mathcal R[3]=\{0,1,2,3,4,6\}+\{0,1,2,3,4,6\}=\{0,1,2,3,4,5,6,7,8,9,10,12\}\subseteq\mathcal R[4]$$

However $$\mathcal R_2[n]\not\subseteq\mathcal R[n+1]$$?

Counter example: $$27,35\in\mathcal R_2[4]\cap \mathcal R[5]^c$$. Also check OEIS A089477.

Denote $$R_2'[n]=\{i\in\mathcal R_2[n]:i\in\mathcal R[n+1]\}$$.

1. Is there an $$\epsilon>0$$ such that $$(2-\epsilon)|R_2'[n]|>|R_2[n]|$$ holds for all $$n$$ bigger than some $$n_0\in\Bbb N$$?

2. If there is no $$\epsilon>0$$ then what is the slowest growing function $$f(n)$$ such that $$f(n)|R_2'[n]|>|R_2[n]|$$ holds for all $$n$$ bigger than some $$n_0\in\Bbb N$$?

• Your question 2 is malformed. Decide on whether script T is a set or a number, and use it consistently. If you consider the subsets which are nonzero mod (k!), and show that they enjoy sufficient properties (all odd numbers below the largest odd are also part of the range, for example), then the result should follow from these sufficient properties. Gerhard "Do Not Overload Your Notation" Paseman, 2017.11.15. Nov 15, 2017 at 18:29
• "..then the result should follow from these sufficient properties" sounds interesting. Can you post what you know? Nov 15, 2017 at 18:43
• I just did. As a guide show (if it can be done) that any positive odd number j less than the largest odd number k in the range for n is also in the range for n. However, if this fails, there may still be a positive answer to the first question. Gerhard "Intervals Are Easier To Understand" Paseman, 2017.11.15. Nov 15, 2017 at 19:08
• For 1: Seems a little unlikely, as it feels like saying that $pc(f),pc(g) \leq n$ implies $pc(f+g) \leq n+1$ (where pc=permanental complexity), whereas it's probably close to tight that $pc(f+g) \leq 2n+1$... What's the crucial difference between that and the 0-1 setting that would allow your Q1 to have a positive answer? Have you tried computer experiments, even to check if $R_2(4) \subseteq R(5)$, for example? Nov 15, 2017 at 23:33
• @Turbo: Evidence for 2n+1: if we replace pc with formula size $F$, surely there are $f,g$ s.t. $F(f+g) = F(f) + F(g) + 1$ - probably random functions should work. Connection between your Q and pc: We could define "pc" of a number as $pc(n) = \min \{m : \exists A \in \{0,1\}^{m \times m} perm(A) = n\}$, and then your question is precisely "If $pc(a),pc(b) \leq n$, does that imply $pc(a+b) \leq n+1$?" Obviously formulas and integers are different, but there's still some connection; e.g., there is an analogue of circuit complexity for integers, e.g. here. Nov 16, 2017 at 17:15

I believe the conjecture is false. Following up on Grochow's recommendation, Mathematica computations show $$\mathcal{R}[4] = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 18, 24 \}$$ so that \begin{align} \mathcal{R}_2[4] = \{&0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, \\&22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 42, 48 \}.\end{align} But (after some hours) \begin{align} \mathcal{R}[5] = \{&0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, \\&22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 42, 44, \\&46, 48, 50, 53, 54, 60, 64, 72, 78, 96, 120\}. \end{align} In particular, $27, 35 \in \mathcal{R}_2[4]$ but neither is in $\mathcal{R}[5]$.
Concerning the sufficient condition $\{0,1,2,\dots,2(n!)\} \subseteq \mathcal{R}[n+1]$, note that 27, 35, 37, 41, 43, 45, 47 are all missing from $\mathcal{R}[5]$.
Mathematica code for $\mathcal{R}[5]$:
• @GerhardPaseman: $\begin{pmatrix} 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{pmatrix}$ has permanent 29 (and is symmetric too). Nov 17, 2017 at 13:45