Asymptotic counting exponent for partial Hadamard matrices

Description of constant

For integers $n\ge 2$ and $t\ge 1$, an $n\times t$ partial Hadamard matrix is a matrix with entries in $\pm 1$ whose rows are pairwise orthogonal. Let $N_{n,t}$ denote the number of such matrices. For every fixed $n$ one has $$N_{n,4t}=[1+o(1)]A_{n,4t}\text{as }t\to \infty ,$$ where $$A_{n,4t}:=2^{4nt+(n-1{)}^2}(8\pi t{)}^{-n(n-1)/4}.$$ <a href="#Davis2026-def-partial">[Davis2026-def-partial]</a> <a href="#Davis2026-fixed-n-A">[Davis2026-fixed-n-A]</a>

Historically, de Launey–Levin proved the fixed-$n$ asymptotic $N_{n,4t}\sim A_{n,4t}$; Canfield later obtained the uniform regime $t/n^4\to \infty$; and the current best result improves this to $t/n^3\to \infty$ and shows that $N_{n,4t}/A_{n,4t}$ does not converge to $1$ when $t=\Theta n^3$ with $\Theta$ large fixed. Thus the remaining open problem is to determine the correct asymptotics of $N_{n,4t}$ below the cubic scale. <a href="#Davis2026-fixed-n-A">[Davis2026-fixed-n-A]</a> <a href="#Can2011">[Can2011]</a> <a href="#Davis2026-prior-exponents">[Davis2026-prior-exponents]</a> <a href="#Davis2026-change-cubic">[Davis2026-change-cubic]</a> <a href="#Davis2026-open-below3">[Davis2026-open-below3]</a>

We define $C_{23c}$ to be the smallest admissible exponent $\alpha \ge 1$ for which the count $N_{n,4t}$ admits a uniform asymptotic formula throughout the regime $t/n^{\alpha }\to \infty$. The restriction $\alpha \ge 1$ is forced by the linear-algebra obstruction $4t\ge n$. The current best-established range is $$1\le C_{23c}\le 3.$$ <a href="#DL2010-linear-obstruction">[DL2010-linear-obstruction]</a> <a href="#Davis2026-open-below3">[Davis2026-open-below3]</a> <a href="#Davis2026-abstract-cubic">[Davis2026-abstract-cubic]</a>

Known upper bounds

Known lower bounds

Additional comments and links

• What is already solved. The narrower problem of determining when the leading term $A_{n,4t}$ alone is asymptotically correct has exact answer $3$. What remains open is whether a corrected asymptotic formula already holds for some exponent below $3$. <a href="#Davis2026-figure2">[Davis2026-figure2]</a> <a href="#Davis2026-change-cubic">[Davis2026-change-cubic]</a>

• Relation to the Hadamard conjecture. The full Hadamard problem sits at the linear endpoint $4t=n$: the Hadamard conjecture is equivalent to $N_{n,n}>0$ whenever $n$ is divisible by $4$. <a href="#Davis2026-hadamard-nn">[Davis2026-hadamard-nn]</a>

• Fixed-$n$ versus uniform counting. The main difficulty is to keep control when $n$ grows with $t$. <a href="#Davis2026-fixed-n-A">[Davis2026-fixed-n-A]</a> <a href="#Davis2026-hadamard-nn">[Davis2026-hadamard-nn]</a>

• Historical formulation of the hard regime. de Launey–Levin already singled out sharper estimates “in the region close to $t=n$” as an important open problem. <a href="#DL2010-near-t=n-open">[DL2010-near-t=n-open]</a>

References

• <a id="Davis2026"></a>[Davis2026] Davis, Damek. Counting partial Hadamard matrices in the cubic regime. arXiv:2603.30013 (2026). DOI: 10.48550/arXiv.2603.30013. arXiv PDF: arXiv:2603.30013. Google Scholar
• <a id="Davis2026-abstract-cubic"></a>[Davis2026-abstract-cubic] loc: arXiv v1 PDF p.1, Abstract. quote: “We give a precise asymptotic formula for the number of $n\times 4t$ partial Hadamard matrices in the regimes $t/n^3\to \infty$ and $t/n^3\to \Theta$ for sufficiently large fixed $\Theta$. This strengthens earlier results of de Launey and Levin, who obtained the asymptotic for $t/n^{12}\to \infty$, and of Canfield, who extended this to $t/n^4\to \infty$.”
• <a id="Davis2026-def-partial"></a>[Davis2026-def-partial] loc: arXiv v1 PDF p.1, Section 1 (Introduction), opening paragraphs. quote: “Rather than constructing full Hadamard matrices, one can study partial ones: an $n\times t$ matrix with entries in $\pm 1$ is a partial Hadamard matrix if its rows are pairwise orthogonal. Partial Hadamard matrices of width nearly $2n$ are known to exist for large $n$ by combining constructions from combinatorial design theory [4, 5] with analytic number theory [7] (see [6, Theorem A]). While these results settle existence for widths close to $2n$, a finer question is to determine how many partial Hadamard matrices there are as a function of $n$ and $t$.”
• <a id="Davis2026-fixed-n-A"></a>[Davis2026-fixed-n-A] loc: arXiv v1 PDF p.2, Section 1 (Introduction), paragraph preceding Theorem 1.1. quote: “Using this framework, De Launey and Levin [6, Theorem 2] proved that for every fixed $n\ge 2$, the number of $n\times 4t$ partial Hadamard matrices satisfies $$N_{n,4t}=[1+o(1)]A_{n,4t}\text{ as }t\to \infty ,$$ where $A_{n,s}:=2^{ns+2d-n+1}(2\pi s{)}^{-d/2}$.”
• <a id="Davis2026-hadamard-nn"></a>[Davis2026-hadamard-nn] loc: arXiv v1 PDF p.2, Section 1 (Introduction), paragraph preceding Theorem 1.1. quote: “Since the Hadamard conjecture is equivalent to $N_{n,n}>0$ whenever $n$ is divisible by $4$, one can also ask what happens when $n$ grows with $t$, potentially at a slower rate: does $N_{n,4t}\sim A_{n,4t}$ still hold, and if so, with what corrections?”
• <a id="Davis2026-prior-exponents"></a>[Davis2026-prior-exponents] loc: arXiv v1 PDF p.2, Section 1 (Introduction), paragraph preceding Theorem 1.1. quote: “Two prior works address this in the regime $t/n^{\alpha }\to \infty$: (i) De Launey and Levin’s proofs [6, Theorem 4.1] give $N_{n,4t}\sim A_{n,4t}$ as $t/n^{12}\to \infty$, though this is never explicitly stated. (ii) Canfield [2] established the same asymptotic as $t/n^4\to \infty$ in unpublished work.”
• <a id="Davis2026-open-below3"></a>[Davis2026-open-below3] loc: arXiv v1 PDF p.2, Section 1 (Introduction), discussion following Theorem 1.1. quote: “Thus the expansion captures the first deviation of $N_{n,4t}$ from the scale $A_{n,4t}$. Below $\alpha =3$ the asymptotics of $N_{n,4t}$ are open (Figure 2).”
• <a id="Davis2026-figure2"></a>[Davis2026-figure2] loc: arXiv v1 PDF p.3, Figure 2 caption. quote: “Each marker indicates the smallest $\alpha$ for which the corresponding work establishes $N_{n,4t}\sim A_{n,4t}$ as $t/n^{\alpha }\to \infty$. Corollary 4.1 extends this to $\alpha =3$. Theorem 1.1 further shows that $N_{n,4t}/A_{n,4t}$ has a nonvanishing correction when $t/n^3$ converges to a constant.”
• <a id="Davis2026-change-cubic"></a>[Davis2026-change-cubic] loc: arXiv v1 PDF p.22, end of Section 4 (after Corollary 4.1). quote: “Thus $N_{n,4t}\sim A_{n,4t}$ as $t/n^3\to \infty$. Conversely, when $t=\Theta n^3$ with $\Theta \ge C_0$ fixed, the error is $O({\Theta }^{-2}+1/n+e^{-c{n}^2})$, so for $\Theta$ large and $n\to \infty$ the leading correction $1/(48\Theta )$ dominates and $N_{n,4t}/A_{n,4t}$ does not converge to $1$: the asymptotics of $N_{n,4t}$ change at the cubic scale.”

• <a id="Can2011"></a>[Can2011] Canfield, E. Rodney. Counting partial Hadamard matrices. Joint Mathematics Meetings (2011), Preliminary report. JMM archive PDF: [1067-05-1695.pdf](http://jointmathematicsmeetings.org/meetings/national/jmm-archive/1067-05-1695.pdf). Google Scholar

• <a id="DL2010"></a>[DL2010] de Launey, Warwick; Levin, David A. A Fourier-analytic approach to counting partial Hadamard matrices. Cryptography and Communications 2 (2010), no. 2, 307–334. DOI: 10.1007/s12095-010-0033-z. arXiv PDF: arXiv:1003.4003. Google Scholar
• <a id="DL2010-linear-obstruction"></a>[DL2010-linear-obstruction] loc: arXiv v1 PDF p.1, Section 1 (Introduction), definition paragraph. quote: “For non-negative integers $n$ and $t$, a partial Hadamard matrix is an $n\times t$ matrix with $\pm 1$ entries such that the inner product between any two distinct rows equals zero. Note that, since the rows of a partial Hadamard matrix $D$ form a set of $n$ independent $t$-dimensional real vectors, we must have $t\ge n$.”
• <a id="DL2010-near-t=n-open"></a>[DL2010-near-t=n-open] loc: arXiv v1 PDF p.4, Section 1 (Introduction), closing paragraph. quote: “While we have left open the important (and probably difficult) problem of obtaining sharper estimates for the integral in equation (3) in the region close to $t=n$, this paper at the very least introduces an interesting non-symmetric lattice random walk, where an understanding of the early (rather than the asymptotic) behavior of the transition probabilities for the walk is paramount.”

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.