{
  "id": "2309.03878",
  "version": "v1",
  "published": "2023-09-07T17:41:56.000Z",
  "updated": "2023-09-07T17:41:56.000Z",
  "title": "On generalized corners and matrix multiplication",
  "authors": [
    "Kevin Pratt"
  ],
  "comment": "Feedback welcome!",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Suppose that $S \\subseteq [n]^2$ contains no three points of the form $(x,y), (x,y+\\delta), (x+\\delta,y')$, where $\\delta \\neq 0$. How big can $S$ be? Trivially, $n \\le |S| \\le n^2$. Slight improvements on these bounds are obtained from Shkredov's upper bound for the corners problem [Shk06], which shows that $|S| \\le O(n^2/(\\log \\log n)^c)$ for some small $c > 0$, and a construction due to Petrov [Pet23], which shows that $|S| \\ge \\Omega(n \\log n/\\sqrt{\\log \\log n})$. Could it be that for all $\\varepsilon > 0$, $|S| \\le O(n^{1+\\varepsilon})$? We show that if so, this would rule out obtaining $\\omega = 2$ using a large family of abelian groups in the group-theoretic framework of Cohn, Kleinberg, Szegedy and Umans [CU03,CKSU05] (which is known to capture the best bounds on $\\omega$ to date), for which no barriers are currently known. Furthermore, an upper bound of $O(n^{4/3 - \\varepsilon})$ for any fixed $\\varepsilon > 0$ would rule out a conjectured approach to obtain $\\omega = 2$ of [CKSU05]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-07T17:41:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "matrix multiplication",
      "generalized corners",
      "shkredovs upper bound",
      "group-theoretic framework",
      "abelian groups"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}