{
  "id": "1501.06235",
  "version": "v1",
  "published": "2015-01-26T02:19:57.000Z",
  "updated": "2015-01-26T02:19:57.000Z",
  "title": "Probabilistic lower bounds on maximal determinants of binary matrices",
  "authors": [
    "Richard P. Brent",
    "Judy-anne H. Osborn",
    "Warren D. Smith"
  ],
  "comment": "16 pages, 2 tables, 23 references. Shorter version of arXiv:1402.6817v3",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $D(n)$ be the maximal determinant for $n \\times n$ $\\{\\pm 1\\}$-matrices, and ${\\mathcal R}(n) = D(n)/n^{n/2}$ be the ratio of $D(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on $D(n)$ and ${\\mathcal R}(n)$ in terms of the distance $d$ to the nearest (smaller) Hadamard matrix, defined by $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h \\le n$. The lower bounds on ${\\mathcal R}(n)$ are \\[ {\\mathcal R}(n) > \\left(\\frac{2}{\\pi e}\\right)^{d/2} \\;\\text{ if }\\; 1 \\le d \\le 3,\\;\\text{ and} \\] \\[{\\mathcal R}(n) > \\left(\\frac{2}{\\pi e}\\right)^{d/2} \\left(1 - d^2\\left(\\frac{\\pi}{2h}\\right)^{1/2}\\right) \\;\\text{ if }\\; d > 3. \\] Since $d^2/h^{1/2} \\to 0$ as $n \\to \\infty$, the latter bound is close to $(\\pi e/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n \\to \\infty$ with $d$ fixed, except in the cases $d \\in \\{0,1\\}$. For $d \\ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then ${\\mathcal R}(n)$ is bounded below by a positive constant $(\\pi e/2)^{-3/2} > 0.1133$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-01-26T02:19:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B20",
      "05D40",
      "15A15",
      "15B34"
    ],
    "keywords": [
      "probabilistic lower bounds",
      "maximal determinant",
      "binary matrices",
      "hadamard matrix",
      "hadamard upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150106235B"
    }
  }
}