{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Nonexistence of a $Q$-polynomial association scheme with Krein array $\\{2r^2-1, 2r^2-2, r^2+1; 1, 2, r^2-1\\}$ and $r$ odd\n", "\n", "We will show that a $Q$-polynomial association scheme with Krein array $\\{2r^2-1, 2r^2-2, r^2+1; 1, 2, r^2-1\\}$ and $r$ odd does not exist. This Krein array is feasible for all $r \\ge 2$. For $r = 2^j$, this Krein array is realized by the duals of Kasami codes with minimum distance $5$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%display latex\n", "import drg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Such a scheme would have $4r^4$ vertices." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}4 \\, r^{4}$ " ], "text/plain": [ "4*r^4" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r = var(\"r\")\n", "p = drg.QPolyParameters([2*r^2-1, 2*r^2-2, r^2+1], [1, 2, r^2-1])\n", "p.order(expand=True, factor=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since the scheme is $Q$-polynomial, we have $q^1_{13} = q^1_{31} = q^3_{11} = 0$. Additionally, we have $q^1_{11} = 0$." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[0, 0, 0, 0\\right]$ " ], "text/plain": [ "[0, 0, 0, 0]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[p.q[1, 1, 1], p.q[1, 1, 3], p.q[1, 3, 1], p.q[3, 1, 1]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The intersection numbers can be checked to be nonnegative and integral for both even and odd values of $r \\ge 2$." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{aligned}0: &\\ \\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & \\frac{1}{2} \\, {\\left(2 \\, r^{2} - 1\\right)} {\\left(r + 1\\right)} r & 0 & 0 \\\\\n", "0 & 0 & {\\left(2 \\, r^{2} - 1\\right)} {\\left(r^{2} + 1\\right)} & 0 \\\\\n", "0 & 0 & 0 & \\frac{1}{2} \\, {\\left(2 \\, r^{2} - 1\\right)} {\\left(r - 1\\right)} r\n", "\\end{array}\\right) \\\\\n", "1: &\\ \\left(\\begin{array}{rrrr}\n", "0 & 1 & 0 & 0 \\\\\n", "1 & \\frac{1}{4} \\, {\\left(r + 3\\right)} {\\left(r + 2\\right)} {\\left(r - 1\\right)} r & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r + 2\\right)} {\\left(r - 1\\right)} & \\frac{1}{4} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} {\\left(r - 2\\right)} r \\\\\n", "0 & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r + 2\\right)} {\\left(r - 1\\right)} & {\\left(r^{2} + 1\\right)} r^{2} & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r - 1\\right)} r \\\\\n", "0 & \\frac{1}{4} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} {\\left(r - 2\\right)} r & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r - 1\\right)} r & \\frac{1}{4} \\, {\\left(r + 2\\right)} {\\left(r - 1\\right)}^{2} r\n", "\\end{array}\\right) \\\\\n", "2: &\\ \\left(\\begin{array}{rrrr}\n", "0 & 0 & 1 & 0 \\\\\n", "0 & \\frac{1}{4} \\, {\\left(r + 2\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} r & \\frac{1}{2} \\, {\\left(r + 1\\right)} r^{3} & \\frac{1}{4} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} \\\\\n", "1 & \\frac{1}{2} \\, {\\left(r + 1\\right)} r^{3} & {\\left(r^{2} + 2\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} & \\frac{1}{2} \\, {\\left(r - 1\\right)} r^{3} \\\\\n", "0 & \\frac{1}{4} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} r^{2} & \\frac{1}{2} \\, {\\left(r - 1\\right)} r^{3} & \\frac{1}{4} \\, {\\left(r + 1\\right)} {\\left(r - 1\\right)} {\\left(r - 2\\right)} r\n", "\\end{array}\\right) \\\\\n", "3: &\\ \\left(\\begin{array}{rrrr}\n", "0 & 0 & 0 & 1 \\\\\n", "0 & \\frac{1}{4} \\, {\\left(r + 1\\right)}^{2} {\\left(r - 2\\right)} r & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r + 1\\right)} r & \\frac{1}{4} \\, {\\left(r + 2\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} r \\\\\n", "0 & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r + 1\\right)} r & {\\left(r^{2} + 1\\right)} r^{2} & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r + 1\\right)} {\\left(r - 2\\right)} \\\\\n", "1 & \\frac{1}{4} \\, {\\left(r + 2\\right)} {\\left(r + 1\\right)} {\\left(r - 1\\right)} r & \\frac{1}{2} \\, {\\left(r^{2} + 1\\right)} {\\left(r + 1\\right)} {\\left(r - 2\\right)} & \\frac{1}{4} \\, {\\left(r + 1\\right)} {\\left(r - 2\\right)} {\\left(r - 3\\right)} r\n", "\\end{array}\\right) \\\\\\end{aligned}$ " ], "text/plain": [ "0: [ 1 0 0 0]\n", " [ 0 1/2*(2*r^2 - 1)*(r + 1)*r 0 0]\n", " [ 0 0 (2*r^2 - 1)*(r^2 + 1) 0]\n", " [ 0 0 0 1/2*(2*r^2 - 1)*(r - 1)*r]\n", "\n", "1: [ 0 1 0 0]\n", " [ 1 1/4*(r + 3)*(r + 2)*(r - 1)*r 1/2*(r^2 + 1)*(r + 2)*(r - 1) 1/4*(r + 1)*(r - 1)*(r - 2)*r]\n", " [ 0 1/2*(r^2 + 1)*(r + 2)*(r - 1) (r^2 + 1)*r^2 1/2*(r^2 + 1)*(r - 1)*r]\n", " [ 0 1/4*(r + 1)*(r - 1)*(r - 2)*r 1/2*(r^2 + 1)*(r - 1)*r 1/4*(r + 2)*(r - 1)^2*r]\n", "\n", "2: [ 0 0 1 0]\n", " [ 0 1/4*(r + 2)*(r + 1)*(r - 1)*r 1/2*(r + 1)*r^3 1/4*(r + 1)*(r - 1)*r^2]\n", " [ 1 1/2*(r + 1)*r^3 (r^2 + 2)*(r + 1)*(r - 1) 1/2*(r - 1)*r^3]\n", " [ 0 1/4*(r + 1)*(r - 1)*r^2 1/2*(r - 1)*r^3 1/4*(r + 1)*(r - 1)*(r - 2)*r]\n", "\n", "3: [ 0 0 0 1]\n", " [ 0 1/4*(r + 1)^2*(r - 2)*r 1/2*(r^2 + 1)*(r + 1)*r 1/4*(r + 2)*(r + 1)*(r - 1)*r]\n", " [ 0 1/2*(r^2 + 1)*(r + 1)*r (r^2 + 1)*r^2 1/2*(r^2 + 1)*(r + 1)*(r - 2)]\n", " [ 1 1/4*(r + 2)*(r + 1)*(r - 1)*r 1/2*(r^2 + 1)*(r + 1)*(r - 2) 1/4*(r + 1)*(r - 2)*(r - 3)*r]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.pTable(factor=True, simplify=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us check that the case $r = 3$ satisfies the known feasibility conditions. We skip the family nonexistence check since the Krein array of the members of family with $r$ odd is already included." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "p.subs(r == 3).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(r+2)(r^2-1)/4 > 0$ for all $r \\ge 2$, so such triples must exist. The parameters $\\alpha, \\beta, \\gamma, \\delta$ will denote the number of vertices in relations $(1, 3, 1), (2, 3, 3), (3, 1, 1), (3, 3, 3)$, respectively, to $x, y, z$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ " $\\newcommand{\\Bold}[1]{\\mathbf{#1}}-\\frac{1}{2} \\, r^{4} + 2 \\, r^{2} + \\alpha + 3 \\, \\beta + 4 \\, \\delta - \\gamma$ " ], "text/plain": [ "-1/2*r^4 + 2*r^2 + alpha + 3*beta + 4*delta - gamma" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S112 = p.tripleEquations(1, 1, 2, params={'alpha': (1, 3, 1), 'beta': (2, 3, 3), 'gamma': (3, 1, 1), 'delta': (3, 3, 3)})\n", "S112[1, 2, 3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that the above triple intersection number can only be integral when $r$ is even. We thus conclude that a $Q$-polynomial association scheme with Krein array $\\{2r^2-1, 2r^2-2, r^2+1; 1, 2, r^2-1\\}$ and $r$ 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 }