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} \qquad\text{as } t \to \infty,\) where \(A_{n,4t} := 2^{4nt+(n-1)^2}(8\pi t)^{-n(n-1)/4}.\) [Davis2026-def-partial] [Davis2026-fixed-n-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. [Davis2026-fixed-n-A] [Can2011] [Davis2026-prior-exponents] [Davis2026-change-cubic] [Davis2026-open-below3]
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.\) [DL2010-linear-obstruction] [Davis2026-open-below3] [Davis2026-abstract-cubic]
Known upper bounds
| Bound on $C_{23c}$ | Reference | Comments |
|---|---|---|
| $12$ | [DL2010] | Historical first polynomial-range asymptotic-counting bound: the de Launey–Levin argument yields $N_{n,4t} \sim A_{n,4t}$ when $t/n^{12} \to \infty$, although that exponent is not isolated as a standalone theorem in the 2010 paper itself. [Davis2026-prior-exponents] |
| $4$ | [Can2011] | Unpublished improvement due to Canfield: $N_{n,4t} \sim A_{n,4t}$ when $t/n^4 \to \infty$. [Davis2026-prior-exponents] |
| $3$ | [Davis2026] | Current best upper bound: the cubic-regime result proves $N_{n,4t} \sim A_{n,4t}$ for $t/n^3 \to \infty$ and shows that a nonvanishing correction survives when $t = \Theta n^3$ with large fixed $\Theta$, so the asymptotics change at the cubic scale. [Davis2026-change-cubic] [Davis2026-open-below3] |
Known lower bounds
| Bound on $C_{23c}$ | Reference | Comments |
|---|---|---|
| $1$ | [DL2010] | Admissible exponents cannot be below $1$: for any $\alpha<1$, the regime $t/n^\alpha \to \infty$ still includes widths with $4t<n$, where an $n \times 4t$ partial Hadamard matrix cannot exist. [DL2010-linear-obstruction] |
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$. [Davis2026-figure2] [Davis2026-change-cubic]
-
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$. [Davis2026-hadamard-nn]
-
Fixed-$n$ versus uniform counting. The main difficulty is to keep control when $n$ grows with $t$. [Davis2026-fixed-n-A] [Davis2026-hadamard-nn]
-
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. [DL2010-near-t=n-open]
References
- [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
- [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$.”
- [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 ${\pm1}$ 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$.”
- [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}$.”
- [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?”
- [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.”
- [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).”
- [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.”
- [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^{-cn^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.”
-
[Can2011] Canfield, E. Rodney. Counting partial Hadamard matrices. Joint Mathematics Meetings (2011), Preliminary report. JMM archive PDF: 1067-05-1695.pdf. Google Scholar
- [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
- [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 $\pm1$ 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$.”
- [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.”
Contribution notes
Prepared with assistance from GPT-5.4 Pro.