3
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 15 '17 at 18:29
  • $\begingroup$ "..then the result should follow from these sufficient properties" sounds interesting. Can you post what you know? $\endgroup$ – T.... Nov 15 '17 at 18:43
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 15 '17 at 19:08
  • $\begingroup$ 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? $\endgroup$ – Joshua Grochow Nov 15 '17 at 23:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Nov 16 '17 at 17:15
2
$\begingroup$

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]$:

Union[Table[ Permanent[Partition[IntegerDigits[i, 2, 25], 5]], {i, 0, 2^25 - 1}]]

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ That 27 is not in R[5] (and 29 is) is very surprising to me. Can anyone else verify this? Gerhard "Making Permanent Spectrum More Mysterious" Paseman, 2017.11.16. $\endgroup$ – Gerhard Paseman Nov 16 '17 at 18:50
  • 1
    $\begingroup$ Indeed OEIS A089477 confirms 27 is missing. Does someone have a binary 5x5 matrix with permanent of 29? Gerhard "Can It Be Symmetric Too?" Paseman, 2017.11.16. $\endgroup$ – Gerhard Paseman Nov 16 '17 at 18:57
  • $\begingroup$ @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). $\endgroup$ – Brian Hopkins Nov 17 '17 at 13:45
  • $\begingroup$ Thank you @Brian. It would be nice to have a combinatorial (non-exhaustive) proof that 27 is not in R[5]. Gerhard "Doesn't Ask For Much, Mostly" Paseman, 2017.11.17. $\endgroup$ – Gerhard Paseman Nov 17 '17 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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