Few permanents of prime circulants

← Minc’s list

Minc’s list · Conjecture 27

Few permanents of prime circulants

Open

Posed by
Nemeth, Seberry and Shu
First posed
1979

Statement

Posed by E. Nemeth, J. Seberry and M. Shu in 1979, in a paper on the distribution of permanents of cyclic \((0,1)\)-matrices; it is Conjecture 27 in Minc’s 1983 survey.

Conjecture 27. For a prime \(p\), the permanents of the \(p\times p\) \((0,1)\)-circulants attain \(O(p)\) distinct values.

A \((0,1)\)-circulant of order \(p\) is \(A_S=\sum_{s\in S}P^s\) for a subset \(S\subseteq\mathbb Z_p\), where \(P\) is the cyclic shift. The conjecture concerns all \(2^p\) such matrices, with any number of ones per row. Translating \(S\) does not change the permanent, which already gives at most \((2^p-2)/p+2\) values.

Prior progress

  • Nemeth, Seberry and Shu (1979) proved the translation bound above and tabulated small orders.
  • Eades, Praeger and Seberry (1983) observed that replacing \(S\) by \(aS+b\) with \(a\ne0\) also preserves the permanent, and counted the resulting classes of \(k\)-subsets of \(\mathbb Z_p\). For four ones per row this gives at most about \(p^2/24\) values.
  • Bernasconi, Codenotti, Crespi and Resta (1999) proved that circulants with three ones per row take at most \(\lceil p/6\rceil\) values, so the conjecture holds when the row sums are at most \(3\).
  • Resta and Sburlati (2003) proposed a rival conjecture: for each fixed \(k\ge3\), the circulants with \(k\) ones per row take \(p^{k-2}/k!+O(p^{k-3})\) values. For \(k=4\) that would grow quadratically and contradict Conjecture 27. They computed the exact counts for four ones per row for all primes \(p\le31\).

Our progress so far

Let \(V_4(p)\) be the number of distinct permanents of the \(p\times p\) circulants with four ones per row.

  • New exact counts. \(V_4(37)=55\), \(V_4(41)=67\) and \(V_4(43)=74\): at these primes every affine class has its own permanent, as Resta and Sburlati predicted.
  • More than \(p\) values at \(p=53\). \(98\le V_4(53)\le113\), so the circulants of order \(53\) with four ones per row already take more than \(53\) distinct permanents. This finite fact is consistent with the rival conjecture but does not by itself disprove an \(O(p)\) bound.
  • A divisibility law. For every prime \(p\ge5\) and every four-element \(S\), \(\operatorname{per}A_S\equiv 4\sigma_S\pmod{16}\) for an explicit \(\sigma_S\in\{-p,0,p\}\); in particular \(4\) divides every such permanent and none is \(\equiv8\pmod{16}\).

References

  1. E. Nemeth, J. Seberry and M. Shu, On the distribution of the permanent of cyclic (0,1) matrices, Utilitas Math. 16 (1979), 171–182.
  2. P. Eades, C. E. Praeger and J. R. Seberry, Some remarks on the permanents of circulant (0,1) matrices, Utilitas Math. 23 (1983), 145–159.
  3. A. Bernasconi, B. Codenotti, V. Crespi and G. Resta, How fast can one compute the permanent of circulant matrices?, Linear Algebra Appl. 292 (1999), 15–37. doi:10.1016/S0024-3795(99)00012-9
  4. G. Resta and G. Sburlati, On the number of different permanents of some sparse (0,1)-circulant matrices, Linear Algebra Appl. 375 (2003), 197–209. doi:10.1016/S0024-3795(03)00649-9