{
  "id": "1402.6817",
  "version": "v3",
  "published": "2014-02-27T08:03:41.000Z",
  "updated": "2015-01-26T01:56:54.000Z",
  "title": "Lower bounds on maximal determinants of binary matrices via the probabilistic method",
  "authors": [
    "Richard P. Brent",
    "Judy-anne H. Osborn",
    "Warren D. Smith"
  ],
  "comment": "37 pages, 2 tables, 59 references. Added some references in v2, fixed typo in v3",
  "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. We give several new lower bounds on ${\\mathcal R}(n)$ in terms of $d$, where $n = h+d$, $h$ is the order of a Hadamard matrix, and $h$ is maximal subject to $h \\le n$. A relatively simple bound is \\[{\\mathcal R}(n) \\ge \\left(\\frac{2}{\\pi e}\\right)^{d/2} \\left(1 - d^2\\left(\\frac{\\pi}{2h}\\right)^{1/2}\\right) \\;\\text{ for all }\\; n \\ge 1.\\] An asymptotically sharper bound is \\[{\\mathcal R}(n) \\ge \\left(\\frac{2}{\\pi e}\\right)^{d/2} \\exp\\left(d\\left(\\frac{\\pi}{2h}\\right)^{1/2} + \\; O\\left(\\frac{d^{5/3}}{h^{2/3}}\\right)\\right).\\] We also show that \\[{\\mathcal R}(n) \\ge \\left(\\frac{2}{\\pi e}\\right)^{d/2}\\] if $n \\ge n_0$ and $n_0$ is sufficiently large, the threshold $n_0$ being independent of $d$, or for all $n\\ge 1$ if $0 \\le d \\le 3$ (which would follow from the Hadamard conjecture). The proofs depend on the probabilistic method, and generalise previous results that were restricted to the cases $d=0$ and $d=1$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-03-13T23:02:38.000Z",
      "comment": "37 pages, 2 tables, 59 references. Added some references in v2",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2015-01-26T01:56:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B20",
      "05D40",
      "15A15",
      "15B34"
    ],
    "keywords": [
      "lower bounds",
      "maximal determinant",
      "probabilistic method",
      "binary matrices",
      "hadamard upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.6817B"
    }
  }
}