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

Improve this question
$\endgroup$
14
  • $\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, 2017 at 18:29
  • $\begingroup$ "..then the result should follow from these sufficient properties" sounds interesting. Can you post what you know? $\endgroup$
    – Turbo
    Nov 15, 2017 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, 2017 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, 2017 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, 2017 at 17:15

1 Answer 1

Reset to default
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}]]

Improve this answer
$\endgroup$
4
  • 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, 2017 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, 2017 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, 2017 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, 2017 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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