{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Nonexistence of a $Q$-polynomial association scheme with Krein array $\\{r^2 - 4, r^2 - 9, 10, 1; 1, 2, r^2 - 9, r^2 - 4\\}$ and $r \\ne 9$\n", "\n", "Let $Y$ be a tight $4$-design in the Hamming scheme $H(n, q)$ (i.e., an orthogonal array of strength $4$ meeting the Rao bound). [Noda](https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s2-19.3.385) proved that then one of the following holds:\n", "1. $(|Y|, n, q) = (16, 5, 2)$,\n", "2. $(|Y|, n, q) = (243, 11, 3)$, or\n", "3. $(|Y|, n, q) = (9a^2 (9a^2-1)/2, (9a^2+1)/5, 6)$, where $a \\equiv 21, 69 \\pmod{240}$.\n", "\n", "Cases 1 and 2 uniquely determine a binary code with $4$ data bits and one parity bit (i.e., the dual of the binary repetition code of length $5$), and the dual of ternary Golay code, respectively. No examples are known for Case 3.\n", "\n", "[Gavrilyuk, Suda and Vidali](http://arxiv.org/abs/1809.07553) show that a $Q$-polynomial association scheme with $d = 4$ classes and Krein array $\\{9a^2 - 4, 9a^2 - 9, 10, 1; 1, 2, 9a^2 - 9, 9a^2 - 4\\}$ would arise from an example of Case 3. We may write $r = 3a$, thus obtaining the Krein array $\\{r^2 - 4, r^2 - 9, 10, 1; 1, 2, r^2 - 9, r^2 - 4\\}$. Here, we show that no corresponding schemes exist, and consequently also no example of Case 3 exists. Note however that we consider all positive integral values of $r$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import drg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A scheme with the above Krein array would have $r^2 (r^2 - 1)/2$ vertices." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1/2*(r + 1)*(r - 1)*r^2" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r, t = var(\"r t\")\n", "p = drg.QPolyParameters([r^2 - 4, r^2 - 9, 10, 1], [1, 2, r^2 - 9, r^2 - 4])\n", "p.order(factor = True, simplify = True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Such a scheme is $Q$-antipodal, so it has $q^h_{ij} = 0$ whenever $h, i, j$ do not satisfy the triangle inequality, or $h+i+j > 2d$ and $d-h, d-i, d-j$ do not satisfy the triangle inequality." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0: [ 1 0 0 0 0]\n", " [ 0 (r + 2)*(r - 2) 0 0 0]\n", " [ 0 0 1/2*(r + 3)*(r + 2)*(r - 2)*(r - 3) 0 0]\n", " [ 0 0 0 5*(r + 2)*(r - 2) 0]\n", " [ 0 0 0 0 5]\n", "\n", "1: [ 0 1 0 0 0]\n", " [ 1 4 (r + 3)*(r - 3) 0 0]\n", " [ 0 (r + 3)*(r - 3) 1/2*(r + 4)*(r + 3)*(r - 3)*(r - 4) 5*(r + 3)*(r - 3) 0]\n", " [ 0 0 5*(r + 3)*(r - 3) 20 5]\n", " [ 0 0 5*r^6/((r^2 - 4)*(r^2 - 9)) - 5*r^4/(r^2 - 4) - 170*r^4/((r^2 - 4)*(r^2 - 9)) + 125*r^2/(r^2 - 4) + 1845*r^2/((r^2 - 4)*(r^2 - 9)) - 720/(r^2 - 4) - 6480/((r^2 - 4)*(r^2 - 9)) 5 0]\n", "\n", "2: [ 0 0 1 0 0]\n", " [ 0 2 (r + 4)*(r - 4) 10 0]\n", " [ 1 (r + 4)*(r - 4) 1/2*r^4 - 25/2*r^2 + 108 5*(r + 4)*(r - 4) 5]\n", " [ 0 10 5*(r + 4)*(r - 4) 50 0]\n", " [ 0 40*r^2/((r^2 - 4)*(r^2 - 9)) - 40/(r^2 - 4) - 360/((r^2 - 4)*(r^2 - 9)) 5 200*r^2/((r^2 - 4)*(r^2 - 9)) - 200/(r^2 - 4) - 1800/((r^2 - 4)*(r^2 - 9)) 0]\n", "\n", "3: [ 0 0 0 1 0]\n", " [ 0 0 (r + 3)*(r - 3) 4 1]\n", " [ 0 (r + 3)*(r - 3) 1/2*(r + 4)*(r + 3)*(r - 3)*(r - 4) 5*(r + 3)*(r - 3) 0]\n", " [ 1 4 5*(r + 3)*(r - 3) 16 4]\n", " [ 0 1 5*r^6/((r^2 - 4)*(r^2 - 9)) - 5*r^4/(r^2 - 4) - 170*r^4/((r^2 - 4)*(r^2 - 9)) + 125*r^2/(r^2 - 4) + 1845*r^2/((r^2 - 4)*(r^2 - 9)) - 720/(r^2 - 4) - 6480/((r^2 - 4)*(r^2 - 9)) 4 0]\n", "\n", "4: [ 0 0 0 0 1]\n", " [ 0 0 0 (r + 2)*(r - 2) 0]\n", " [ 0 0 1/2*(r + 3)*(r + 2)*(r - 2)*(r - 3) 0 0]\n", " [ 0 (r + 2)*(r - 2) 0 4*(r + 2)*(r - 2) 0]\n", " [ 1 4*r^4/((r^2 - 4)*(r^2 - 9)) - 4*r^2/(r^2 - 4) - 52*r^2/((r^2 - 4)*(r^2 - 9)) + 16/(r^2 - 4) + 144/((r^2 - 4)*(r^2 - 9)) 5*r^6/((r^2 - 4)*(r^2 - 9)) - 5*r^4/(r^2 - 4) - 110*r^4/((r^2 - 4)*(r^2 - 9)) + 65*r^2/(r^2 - 4) + 765*r^2/((r^2 - 4)*(r^2 - 9)) - 180/(r^2 - 4) - 1620/((r^2 - 4)*(r^2 - 9)) 16*r^4/((r^2 - 4)*(r^2 - 9)) - 16*r^2/(r^2 - 4) - 208*r^2/((r^2 - 4)*(r^2 - 9)) + 64/(r^2 - 4) + 576/((r^2 - 4)*(r^2 - 9)) 4]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.kreinParameters(factor = True, simplify = True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The intersection numbers can be checked to be nonnegative and integral for odd values of $r \\ge 5$." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0: [ 1 0 0 0 0]\n", " [ 0 5/24*(r + 1)*(r - 1)*(r - 2)*r 0 0 0]\n", " [ 0 0 1/24*(r + 3)*(r + 2)*(r + 1)*(r - 2) 0 0]\n", " [ 0 0 0 5/24*(r + 2)*(r + 1)*(r - 1)*r 0]\n", " [ 0 0 0 0 1/24*(r + 2)*(r - 1)*(r - 2)*(r - 3)]\n", "\n", "1: [ 0 1 0 0 0]\n", " [ 1 1/12*(r^2 - 3*r + 6)*(r + 1)*(r - 1) 1/48*(r + 3)*(r + 2)*(r + 1)*(r - 3) 1/12*(r + 2)*(r + 1)*(r - 1)*(r - 3) 1/48*(r + 2)*(r - 1)*(r - 3)*(r - 5)]\n", " [ 0 1/48*(r + 3)*(r + 2)*(r + 1)*(r - 3) 0 1/48*(r + 3)*(r + 2)*(r + 1)*(r - 1) 0]\n", " [ 0 1/12*(r + 2)*(r + 1)*(r - 1)*(r - 3) 1/48*(r + 3)*(r + 2)*(r + 1)*(r - 1) 1/12*(r + 3)*(r + 2)*(r + 1)*(r - 1) 1/48*(r + 2)*(r + 1)*(r - 1)*(r - 3)]\n", " [ 0 1/48*(r + 2)*(r - 1)*(r - 3)*(r - 5) 0 1/48*(r + 2)*(r + 1)*(r - 1)*(r - 3) 0]\n", "\n", "2: [ 0 0 1 0 0]\n", " [ 0 5/48*(r + 1)*(r - 1)*(r - 3)*r 0 5/48*(r + 1)*(r - 1)^2*r 0]\n", " [ 1 0 1/48*(r^2 + 3*r - 12)*(r + 5)*(r + 1) 0 1/48*(r + 4)*(r - 1)^2*(r - 3)]\n", " [ 0 5/48*(r + 1)*(r - 1)^2*r 0 5/48*(r + 5)*(r + 1)*(r - 1)*r 0]\n", " [ 0 0 1/48*(r + 4)*(r - 1)^2*(r - 3) 0 1/48*(r + 1)*(r - 1)*(r - 3)*(r - 4)]\n", "\n", "3: [ 0 0 0 1 0]\n", " [ 0 1/12*(r + 1)*(r - 1)*(r - 2)*(r - 3) 1/48*(r + 3)*(r + 1)*(r - 1)*(r - 2) 1/12*(r + 3)*(r + 1)*(r - 1)*(r - 2) 1/48*(r + 1)*(r - 1)*(r - 2)*(r - 3)]\n", " [ 0 1/48*(r + 3)*(r + 1)*(r - 1)*(r - 2) 0 1/48*(r + 5)*(r + 3)*(r + 1)*(r - 2) 0]\n", " [ 1 1/12*(r + 3)*(r + 1)*(r - 1)*(r - 2) 1/48*(r + 5)*(r + 3)*(r + 1)*(r - 2) 1/12*(r^2 + 3*r + 6)*(r + 1)*(r - 1) 1/48*(r + 3)*(r - 1)*(r - 2)*(r - 3)]\n", " [ 0 1/48*(r + 1)*(r - 1)*(r - 2)*(r - 3) 0 1/48*(r + 3)*(r - 1)*(r - 2)*(r - 3) 0]\n", "\n", "4: [ 0 0 0 0 1]\n", " [ 0 5/48*(r + 1)*(r - 1)*(r - 5)*r 0 5/48*(r + 1)^2*(r - 1)*r 0]\n", " [ 0 0 1/48*(r + 4)*(r + 3)*(r + 1)*(r - 1) 0 1/48*(r + 3)*(r + 1)^2*(r - 4)]\n", " [ 0 5/48*(r + 1)^2*(r - 1)*r 0 5/48*(r + 3)*(r + 1)*(r - 1)*r 0]\n", " [ 1 0 1/48*(r + 3)*(r + 1)^2*(r - 4) 0 1/48*(r^2 - 3*r - 12)*(r - 1)*(r - 5)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.pTable(factor = True, simplify = True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now compute the triple intersection numbers with respect to three vertices $x, y, z$ mutually in relation $1$. Note that we have $p^1_{11} = (r^2 - 3r + 6)(r^2 - 1)/12 > 0$ for all $r \\ge 5$, so such triples must exist. The parameter $A$ will denote the number of vertices in relations $1, 2, 3$ to $x, y, z$, respectively." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1/16*(r^5 + 2*r^3 - 3*(16*A + 1)*r - 18*r^2 + 18)/r" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S111 = p.tripleEquations(1, 1, 1, params={'A': (1, 2, 3)})\n", "S111[1, 1, 1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The above triple intersection number is integral for odd values of $r$ whenever $5r + 4 - 9/r$ is divisible by $8$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "t^4 + 2*t^3 + 2*t^2 - 3*A" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(S111[1, 1, 1] + (5*r + 4 - 9/r)/8).subs(r == 2*t + 1).factor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The above expression is integral only when $r$ divides $9$. As we must have $r \\ge 5$, we conclude that a $Q$-polynomial association scheme with Krein array $\\{r^2 - 4, r^2 - 9, 10, 1; 1, 2, r^2 - 9, r^2 - 4\\}$ and $r \\ne 9$ **does not exist**. Consequently, no tight $4$-design in $H((9a^2+1)/5, 6)$ exists, thus completing the classification of orthogonal arrays of strength $4$ meeting the Rao bound.\n", "\n", "The case $r = 9$ with Krein array $\\{77, 72, 10, 1; 1, 2, 72, 77\\}$ remains feasible. Such a scheme would have a strongly regular graph with parameters $(v, k, \\lambda, \\mu) = (540, 154, 28, 50)$ as a subscheme. This parameter set is feasible, however no example is known." ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.2.beta8", "language": "", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 2 }