TheoremDB
All problems

[#P2598] Rank log-concavity for symmetric binary matrices through order fifty

Work on this problem in ChatGPT
A mathematical schematic of Rank log-concavity for symmetric binary matrices through order fifty.
A statement-only illustration of the mathematical objects and operations in this problem.

Problem. For \(1\le n\le50\), let \(R_{n,r}\) count symmetric \(n\times n\) matrices over \(\mathbb F_2\) of rank \(r\). Is \((R_{n,0},R_{n,1},\ldots,R_{n,n})\) log-concave for every such \(n\)?

1Context

The target is a finite formula-audit and integer-inequality sweep. Exhaustive enumeration has reached n=6; product formulas should extend the check without enumerating matrices.

2Remarks

Remark 1. The diagonal entries are unrestricted, so there are 2^{n(n+1)/2} matrices.

Remark 2. Rank is computed over the field with two elements.

3What counts as a solution

  • Give exact rank counts and all adjacent log-concavity checks through n=50, or give the first violating n and rank.

1The answerReproducednot Lean-verified

Answer (The symmetric binary rank distribution is strictly log-concave). Adjacent quotients from the exact rank formula decrease strictly, proving every requested inequality and the same result in all orders.[2]

Verification

Let \(R_{n,r}\) count symmetric \(n\times n\) matrices over \(\mathbb F_2\) of rank \(r\), with unrestricted diagonal. Put \(Q_{n,r}=R_{n,r+1}/R_{n,r}\) for \(0\leq r<n\). Substitution in the MacWilliams formula gives \[ Q_{n,2s}=2^{n-2s}-1 \] and \[ Q_{n,2s+1}=\frac{2^{2s+2}}{2^{2s+2}-1}\left(2^{n-2s-1}-1\right). \] These quotients decrease strictly. At an even internal rank \(2s\), the preceding quotient has both a larger power-of-two factor and a multiplier greater than one: \[ Q_{n,2s-1}=\frac{2^{2s}}{2^{2s}-1}\left(2^{n-2s+1}-1\right)>2^{n-2s}-1=Q_{n,2s}. \] At an odd internal rank \(2s+1\), write \(a=n-2s-1\geq1\). Since \(2^{2s+2}/(2^{2s+2}-1)\leq4/3\), \[ Q_{n,2s+1}\leq\frac43(2^a-1)<2^{a+1}-1=Q_{n,2s}. \] Thus \(Q_{n,r-1}>Q_{n,r}\), which is equivalent to \[ R_{n,r}^2>R_{n,r-1}R_{n,r+1} \] for every \(n\geq2\) and \(1\leq r<n\). In particular, all 1,225 inequalities requested for \(1\leq n\leq50\) hold strictly.

1Records

4 records

Notes and companion materialContext, examples, and computations

Original intake status. SOLVED in the independently reviewed TheoremDB packet as of 2026-08-01. Adjacent quotients from the exact rank formula decrease strictly, proving every requested inequality and the same result in all orders.

  • Independent isolated execution completed successfully for Replayable exact rank and log-concavity sweep. Every embedded assertion passed and the run reproduced the selected exact result: Adjacent quotients from the exact rank formula decrease strictly, proving every requested inequality and the same result in all orders.
  • Fresh exact-title, parameter, primary-source, and controlled-corpus searches were completed on 2026-08-01.

Recorded example 1. For n=5 the rank counts are 1,31,620,4340,13888,13888.

Computational notes

  • Exact enumeration of all upper-triangular bit patterns was completed for 1 <= n <= 6. The rank vectors were [1,1], [1,3,4], [1,7,28,28], [1,15,140,420,448], [1,31,620,4340,13888,13888], and [1,63,2604,39060,291648,874944,888832]. Every vector was log-concave.
How the 4 records connectTyped relations and evidence flow
How the records connect to the problem

ProblemRank log-concavity for symmetric binary matrices through order fifty

2See also

How to cite

TheoremDB contributors, “Rank log-concavity for symmetric binary matrices through order fifty,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/symmetric-binary-matrix-rank-log-concavity

This problem includes 4 records joined by 4 typed links, sourced from doi.org[2], current as of July 25, 2026.

1Lean verification

Lean formalization needed

An informal proof is recorded. A Lean formalization still needs to be attached. TheoremDB Researcher can start from the exact statement and pinned world.

Open TheoremDB Researcher

The prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.

1References

  1. Joel Brewster Lewis, Ricky Ini Liu, Alejandro H. Morales, Greta Panova, Steven V. Sam, and Yan X. Zhang, “Matrices with Restricted Entries and q-Analogues of Permutations,” Journal of Combinatorics 2(3) (2011), 355-395. DOI 10.4310/JOC.2011.v2.n3.a2. Inline Python 3 exact computation executed on 2026-07-25. preprint · primary source · arXiv:1011.4539, version checked 2026-08-01 · checked 2026-08-01Source use: original summary.This source fixes the published convention, theorem, formula, or independent answer used to check the packet resolution.Also cited at Joel Brewster Lewis, Ricky Ini Liu, Alejandro H. Morales, Greta Panova, Steven V. Sam, and Yan X. Zhang, Matrices with Restricted Entries and q-Analogues of Permutations, Journal of Combinatorics 2(3) (2011), Equation (4.5), Remark 4.1, and the definitions preceding Proposition 4.12; the formula is attributed there to MacWilliams, Theorem 2.For Rank log-concavity for symmetric binary matrices through order fifty, the reviewed source scope is Joel Brewster Lewis, Ricky Ini Liu, Alejandro H. Morales, Greta Panova, Steven V. Sam, and Yan X. Zhang, Matrices with Restricted Entries and q-Analogues of Permutations, Journal of Combinatorics 2(3) (2011), Equation (4.5), Remark 4.1, and the definitions preceding Proposition 4.12; the formula is attributed there to MacWilliams, Theorem 2. The packet makes no inference beyond that cited scope.
  2. Packet source. Jessie MacWilliams, “Orthogonal Matrices Over Finite Fields”. The American Mathematical Monthly 76(2) (1969), 152-164. DOI 10.1080/00029890.1969.12000160. F. Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, American Mathematical Monthly 76(2) (1969), 152-164, Theorem 2; Joel Brewster Lewis et al., Matrices with Restricted Entries and q-Analogues of Permutations, Journal of Combinatorics 2(3) (2011), 355-395, Equation (4.5) and the definitions preceding Proposition 4.12, arXiv:1011.4539. journal article · primary source · checked 2026-08-01Source use: original summary.For Rank log-concavity for symmetric binary matrices through order fifty: The unrestricted-diagonal formula specializes cleanly to characteristic two and reproduces the candidate's enumerated rows.Also cited at Exact adjacent-quotient argument from the audited MacWilliams formula, replayed in sbmrlc-artifact-exact-sweep.Source named by the research packet.

Coefficient inequality target for the exact rank distribution of a finite random-matrix model.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.