{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Nonexistence of a $Q$-polynomial association scheme with Krein array $\\{m, m-1, m(r^2-1)/r^2, m-r^2+1; 1, m/r^2, r^2-1, m\\}$ and $m$ odd\n", "\n", "We show that a $Q$-polynomial association scheme with Krein array $\\{m, m-1, m(r^2-1)/r^2, m-r^2+1; 1, m/r^2, r^2-1, m\\}$ and $m$ odd does not exist. This Krein array is feasible for all integers $m$ and $r$ such that $0 < 2(r^2-1) \\le m \\le r(r-1)(r+2)$ and $m(r+1)$ is even. A scheme with such a Krein array has a (pseudo)-Latin square strongly regular graph with parameters $(v, k, \\lambda, \\mu) = (m^2, (m-1)r^2, m + r^2(r^2-3), r^2(r^2-1))$ as its $Q$-polynomial quotient. Therefore, we say that such a scheme is of *Latin square type*.\n", "\n", "There are several examples of $Q$-polynomial association schemes with such a Krein array. For $(r, m) = (2, 6)$ and $(r, m) = (3, 16)$, this Krein array is realized by the schemes of roots of the lattices $E_6$ and OBW16. For $(r, m) = (2^{ij}, 2^{i(2j+1)})$, there are $\\phi(2j+1)/2$ non-isomorphic examples arising from Kasami codes for each choice of positive integers $i$ and $j$ (here, $\\phi$ represents Euler's totient function). In particular, the Krein array obtained by setting $i = j = 1$ uniquely determines the halved $8$-cube.\n", "\n", "In the case when $r$ is a prime power and $m = r^3$, the formal dual of this parameter set (i.e., a distance-regular graph with the corresponding intersection array) is realized by a Pasechnik graph." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%display latex\n", "import drg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Such a scheme would have $2m^2$ vertices." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}2 \\, m^{2}$ " ], "text/plain": [ "2*m^2" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m, r = var(\"m r\")\n", "p = drg.QPolyParameters([m, m-1, m*(r^2-1)/r^2, m-r^2+1], [1, m/r^2, r^2-1, m])\n", "p.order(factor=True, simplify=2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This scheme is $Q$-bipartite, so it has $q^h_{ij} = 0$ whenever $h+i+j$ is odd, or $h, i, j$ do not satisfy the triangle inequality." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{aligned}0: &\\ \\left(\\begin{array}{rrrrr}\n", "1 & 0 & 0 & 0 & 0 \\\\\n", "0 & m & 0 & 0 & 0 \\\\\n", "0 & 0 & {\\left(m - 1\\right)} r^{2} & 0 & 0 \\\\\n", "0 & 0 & 0 & {\\left(m - 1\\right)} m & 0 \\\\\n", "0 & 0 & 0 & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(m - 1\\right)}\n", "\\end{array}\\right) \\\\\n", "1: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 1 & 0 & 0 & 0 \\\\\n", "1 & 0 & m - 1 & 0 & 0 \\\\\n", "0 & m - 1 & 0 & {\\left(m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 \\\\\n", "0 & 0 & {\\left(m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(m - 1\\right)} \\\\\n", "0 & 0 & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(m - 1\\right)} & 0\n", "\\end{array}\\right) \\\\\n", "2: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 0 & 1 & 0 & 0 \\\\\n", "0 & \\frac{m}{r^{2}} & 0 & \\frac{m {\\left(r + 1\\right)} {\\left(r - 1\\right)}}{r^{2}} & 0 \\\\\n", "1 & 0 & r^{4} - 3 \\, r^{2} + m & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} \\\\\n", "0 & \\frac{m {\\left(r + 1\\right)} {\\left(r - 1\\right)}}{r^{2}} & 0 & \\frac{{\\left(m r^{2} - 2 \\, r^{2} + 1\\right)} m}{r^{2}} & 0 \\\\\n", "0 & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 & {\\left(r^{2} - m\\right)} {\\left(r^{2} - m - 1\\right)}\n", "\\end{array}\\right) \\\\\n", "3: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 0 & 0 & 1 & 0 \\\\\n", "0 & 0 & {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 & -r^{2} + m + 1 \\\\\n", "0 & {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 & m r^{2} - 2 \\, r^{2} + 1 & 0 \\\\\n", "1 & 0 & m r^{2} - 2 \\, r^{2} + 1 & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(m - 2\\right)} \\\\\n", "0 & -r^{2} + m + 1 & 0 & -{\\left(r^{2} - m - 1\\right)} {\\left(m - 2\\right)} & 0\n", "\\end{array}\\right) \\\\\n", "4: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & m & 0 \\\\\n", "0 & 0 & {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} & 0 & -{\\left(r^{2} - m\\right)} r^{2} \\\\\n", "0 & m & 0 & {\\left(m - 2\\right)} m & 0 \\\\\n", "1 & 0 & -{\\left(r^{2} - m\\right)} r^{2} & 0 & r^{4} - 2 \\, m r^{2} + m^{2} + r^{2} - 2\n", "\\end{array}\\right) \\\\\\end{aligned}$ " ], "text/plain": [ "0: [ 1 0 0 0 0]\n", " [ 0 m 0 0 0]\n", " [ 0 0 (m - 1)*r^2 0 0]\n", " [ 0 0 0 (m - 1)*m 0]\n", " [ 0 0 0 0 -(r^2 - m - 1)*(m - 1)]\n", "\n", "1: [ 0 1 0 0 0]\n", " [ 1 0 m - 1 0 0]\n", " [ 0 m - 1 0 (m - 1)*(r + 1)*(r - 1) 0]\n", " [ 0 0 (m - 1)*(r + 1)*(r - 1) 0 -(r^2 - m - 1)*(m - 1)]\n", " [ 0 0 0 -(r^2 - m - 1)*(m - 1) 0]\n", "\n", "2: [ 0 0 1 0 0]\n", " [ 0 m/r^2 0 m*(r + 1)*(r - 1)/r^2 0]\n", " [ 1 0 r^4 - 3*r^2 + m 0 -(r^2 - m - 1)*(r + 1)*(r - 1)]\n", " [ 0 m*(r + 1)*(r - 1)/r^2 0 (m*r^2 - 2*r^2 + 1)*m/r^2 0]\n", " [ 0 0 -(r^2 - m - 1)*(r + 1)*(r - 1) 0 (r^2 - m)*(r^2 - m - 1)]\n", "\n", "3: [ 0 0 0 1 0]\n", " [ 0 0 (r + 1)*(r - 1) 0 -r^2 + m + 1]\n", " [ 0 (r + 1)*(r - 1) 0 m*r^2 - 2*r^2 + 1 0]\n", " [ 1 0 m*r^2 - 2*r^2 + 1 0 -(r^2 - m - 1)*(m - 2)]\n", " [ 0 -r^2 + m + 1 0 -(r^2 - m - 1)*(m - 2) 0]\n", "\n", "4: [ 0 0 0 0 1]\n", " [ 0 0 0 m 0]\n", " [ 0 0 (r + 1)*(r - 1)*r^2 0 -(r^2 - m)*r^2]\n", " [ 0 m 0 (m - 2)*m 0]\n", " [ 1 0 -(r^2 - m)*r^2 0 r^4 - 2*m*r^2 + m^2 + r^2 - 2]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.kreinParameters(factor=True, simplify=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Krein parameters and intersection numbers can be checked to be nonnegative for all integers $m$ and $r$ such that $1 < r^2 \\le m \\le r(r-1)(r+2)$. The intersection numbers are integral when $r$ is odd - however, when it is even, $m$ must also be even." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{aligned}0: &\\ \\left(\\begin{array}{rrrrr}\n", "1 & 0 & 0 & 0 & 0 \\\\\n", "0 & {\\left(m - 1\\right)} r^{2} & 0 & 0 & 0 \\\\\n", "0 & 0 & -2 \\, {\\left(r^{2} - m - 1\\right)} {\\left(m - 1\\right)} & 0 & 0 \\\\\n", "0 & 0 & 0 & {\\left(m - 1\\right)} r^{2} & 0 \\\\\n", "0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right) \\\\\n", "1: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 1 & 0 & 0 & 0 \\\\\n", "1 & \\frac{1}{2} \\, {\\left(r^{3} - r^{2} + m - 2 \\, r\\right)} {\\left(r + 1\\right)} & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & \\frac{1}{2} \\, {\\left(r^{3} + r^{2} - m - 2 \\, r\\right)} {\\left(r - 1\\right)} & 0 \\\\\n", "0 & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 2 \\, {\\left(r^{2} - m\\right)} {\\left(r^{2} - m - 1\\right)} & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 \\\\\n", "0 & \\frac{1}{2} \\, {\\left(r^{3} + r^{2} - m - 2 \\, r\\right)} {\\left(r - 1\\right)} & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & \\frac{1}{2} \\, {\\left(r^{3} - r^{2} + m - 2 \\, r\\right)} {\\left(r + 1\\right)} & 1 \\\\\n", "0 & 0 & 0 & 1 & 0\n", "\\end{array}\\right) \\\\\n", "2: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 0 & 1 & 0 & 0 \\\\\n", "0 & \\frac{1}{2} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} & -{\\left(r^{2} - m\\right)} r^{2} & \\frac{1}{2} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} & 0 \\\\\n", "1 & -{\\left(r^{2} - m\\right)} r^{2} & 2 \\, r^{4} - 4 \\, m r^{2} + 2 \\, m^{2} + 2 \\, r^{2} - 4 & -{\\left(r^{2} - m\\right)} r^{2} & 1 \\\\\n", "0 & \\frac{1}{2} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} & -{\\left(r^{2} - m\\right)} r^{2} & \\frac{1}{2} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} & 0 \\\\\n", "0 & 0 & 1 & 0 & 0\n", "\\end{array}\\right) \\\\\n", "3: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 0 & 0 & 1 & 0 \\\\\n", "0 & \\frac{1}{2} \\, {\\left(r^{3} + r^{2} - m - 2 \\, r\\right)} {\\left(r - 1\\right)} & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & \\frac{1}{2} \\, {\\left(r^{3} - r^{2} + m - 2 \\, r\\right)} {\\left(r + 1\\right)} & 1 \\\\\n", "0 & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 2 \\, {\\left(r^{2} - m\\right)} {\\left(r^{2} - m - 1\\right)} & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & 0 \\\\\n", "1 & \\frac{1}{2} \\, {\\left(r^{3} - r^{2} + m - 2 \\, r\\right)} {\\left(r + 1\\right)} & -{\\left(r^{2} - m - 1\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & \\frac{1}{2} \\, {\\left(r^{3} + r^{2} - m - 2 \\, r\\right)} {\\left(r - 1\\right)} & 0 \\\\\n", "0 & 1 & 0 & 0 & 0\n", "\\end{array}\\right) \\\\\n", "4: &\\ \\left(\\begin{array}{rrrrr}\n", "0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & {\\left(m - 1\\right)} r^{2} & 0 \\\\\n", "0 & 0 & -2 \\, {\\left(r^{2} - m - 1\\right)} {\\left(m - 1\\right)} & 0 & 0 \\\\\n", "0 & {\\left(m - 1\\right)} r^{2} & 0 & 0 & 0 \\\\\n", "1 & 0 & 0 & 0 & 0\n", "\\end{array}\\right) \\\\\\end{aligned}$ " ], "text/plain": [ "0: [ 1 0 0 0 0]\n", " [ 0 (m - 1)*r^2 0 0 0]\n", " [ 0 0 -2*(r^2 - m - 1)*(m - 1) 0 0]\n", " [ 0 0 0 (m - 1)*r^2 0]\n", " [ 0 0 0 0 1]\n", "\n", "1: [ 0 1 0 0 0]\n", " [ 1 1/2*(r^3 - r^2 + m - 2*r)*(r + 1) -(r^2 - m - 1)*(r + 1)*(r - 1) 1/2*(r^3 + r^2 - m - 2*r)*(r - 1) 0]\n", " [ 0 -(r^2 - m - 1)*(r + 1)*(r - 1) 2*(r^2 - m)*(r^2 - m - 1) -(r^2 - m - 1)*(r + 1)*(r - 1) 0]\n", " [ 0 1/2*(r^3 + r^2 - m - 2*r)*(r - 1) -(r^2 - m - 1)*(r + 1)*(r - 1) 1/2*(r^3 - r^2 + m - 2*r)*(r + 1) 1]\n", " [ 0 0 0 1 0]\n", "\n", "2: [ 0 0 1 0 0]\n", " [ 0 1/2*(r + 1)*(r - 1)*r^2 -(r^2 - m)*r^2 1/2*(r + 1)*(r - 1)*r^2 0]\n", " [ 1 -(r^2 - m)*r^2 2*r^4 - 4*m*r^2 + 2*m^2 + 2*r^2 - 4 -(r^2 - m)*r^2 1]\n", " [ 0 1/2*(r + 1)*(r - 1)*r^2 -(r^2 - m)*r^2 1/2*(r + 1)*(r - 1)*r^2 0]\n", " [ 0 0 1 0 0]\n", "\n", "3: [ 0 0 0 1 0]\n", " [ 0 1/2*(r^3 + r^2 - m - 2*r)*(r - 1) -(r^2 - m - 1)*(r + 1)*(r - 1) 1/2*(r^3 - r^2 + m - 2*r)*(r + 1) 1]\n", " [ 0 -(r^2 - m - 1)*(r + 1)*(r - 1) 2*(r^2 - m)*(r^2 - m - 1) -(r^2 - m - 1)*(r + 1)*(r - 1) 0]\n", " [ 1 1/2*(r^3 - r^2 + m - 2*r)*(r + 1) -(r^2 - m - 1)*(r + 1)*(r - 1) 1/2*(r^3 + r^2 - m - 2*r)*(r - 1) 0]\n", " [ 0 1 0 0 0]\n", "\n", "4: [ 0 0 0 0 1]\n", " [ 0 0 0 (m - 1)*r^2 0]\n", " [ 0 0 -2*(r^2 - m - 1)*(m - 1) 0 0]\n", " [ 0 (m - 1)*r^2 0 0 0]\n", " [ 1 0 0 0 0]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.set_vars([m, r])\n", "p.pTable(factor=True, simplify=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By the absolute bound for $(1, 1)$, such a scheme is only feasible when $m \\ge 2(r^2-1)$." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{{\\left(1, 1\\right) : -\\frac{1}{2} \\, {\\left(2 \\, r^{2} - m - 2\\right)} {\\left(m - 1\\right)}}, {\\left(1, 2\\right) : {\\left(m r^{2} - r^{2} - m\\right)} m}, {\\left(1, 3\\right) : {\\left(m^{2} - m - 1\\right)} {\\left(m - 1\\right)}}, {\\left(1, 4\\right) : -{\\left(r^{2} - m\\right)} {\\left(m - 1\\right)} m}, {\\left(2, 2\\right) : \\frac{1}{2} \\, m^{2} r^{4} - m r^{4} + \\frac{1}{2} \\, r^{4} + \\frac{1}{2} \\, m r^{2} - m^{2} - \\frac{1}{2} \\, r^{2}}, {\\left(2, 3\\right) : {\\left(m^{2} r^{2} - 2 \\, m r^{2} + r^{2} - m\\right)} m}, {\\left(2, 4\\right) : -{\\left(m r^{4} - m^{2} r^{2} - r^{4} + r^{2} + m + 1\\right)} {\\left(m - 1\\right)}}, {\\left(3, 3\\right) : \\frac{1}{2} \\, {\\left(m^{3} - 2 \\, m^{2} - 1\\right)} m}, {\\left(3, 4\\right) : -{\\left(m^{2} r^{2} - m^{3} - 2 \\, m r^{2} + m^{2} + r^{2} + 2 \\, m - 1\\right)} m}, {\\left(4, 4\\right) : \\frac{1}{2} \\, m^{2} r^{4} - m^{3} r^{2} - m r^{4} + \\frac{1}{2} \\, m^{4} + m^{2} r^{2} + \\frac{1}{2} \\, r^{4} + \\frac{1}{2} \\, m r^{2} - \\frac{3}{2} \\, m^{2} - \\frac{1}{2} \\, r^{2}}\\right\\}$ " ], "text/plain": [ "{(1, 1): -1/2*(2*r^2 - m - 2)*(m - 1),\n", " (1, 2): (m*r^2 - r^2 - m)*m,\n", " (1, 3): (m^2 - m - 1)*(m - 1),\n", " (1, 4): -(r^2 - m)*(m - 1)*m,\n", " (2, 2): 1/2*m^2*r^4 - m*r^4 + 1/2*r^4 + 1/2*m*r^2 - m^2 - 1/2*r^2,\n", " (2, 3): (m^2*r^2 - 2*m*r^2 + r^2 - m)*m,\n", " (2, 4): -(m*r^4 - m^2*r^2 - r^4 + r^2 + m + 1)*(m - 1),\n", " (3, 3): 1/2*(m^3 - 2*m^2 - 1)*m,\n", " (3, 4): -(m^2*r^2 - m^3 - 2*m*r^2 + m^2 + r^2 + 2*m - 1)*m,\n", " (4,\n", " 4): 1/2*m^2*r^4 - m^3*r^2 - m*r^4 + 1/2*m^4 + m^2*r^2 + 1/2*r^4 + 1/2*m*r^2 - 3/2*m^2 - 1/2*r^2}" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.check_absoluteBound(expand=True, factor=True, simplify=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us check that the smallest admissible case with $m$ odd, namely $(r, m) = (3, 17)$, satisfies the known feasibility conditions. We skip the family nonexistence check since the Krein array of the members of family with $r, m$ odd is already included." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "p.subs(r == 3, m == 17).check_feasible(skip=[\"family\"])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now compute the triple intersection numbers with respect to three vertices $x, y, z$ such that $x$ is in relation $1$ with $y$ and $z$, and $y$ is in relation $2$ with $z$. Note that we have $p^2_{11} = r^2 (r^2-1)/2 > 0$ for all $r \\ge 2$, so such triples must exist. The parameter $\\alpha$ will denote the number of vertices in relation $1$ to all of $x, y, z$." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}-\\frac{1}{2} \\, r^{3} + \\frac{1}{2} \\, r^{2} + \\alpha - \\frac{1}{2} \\, m + r$ " ], "text/plain": [ "-1/2*r^3 + 1/2*r^2 + alpha - 1/2*m + r" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S112 = p.tripleEquations(1, 1, 2, params={'alpha': (1, 1, 1)})\n", "S112[1, 1, 3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that the above triple intersection number can only be integral when $m$ is even. We thus conclude that a $Q$-polynomial association scheme with Krein array $\\{m, m-1, m(r^2-1)/r^2, m-r^2+1; 1, m/r^2, r^2-1, m\\}$ and $m$ odd **does not exist**." ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.9.beta2", "language": "sage", "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.15" } }, "nbformat": 4, "nbformat_minor": 2 }