Asymptotic counting exponent for partial Hadamard matrices ($C_{23c}$)

• 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 (from the repository page)

• [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

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.”

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 1; best known upper bound 3. Values marked with an asterisk have minimal verification.

Known upper bounds

Known lower bounds