#!/usr/bin/env python
# coding: utf-8

# # 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$
# 
# 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:
# 1. $(|Y|, n, q) = (16, 5, 2)$,
# 2. $(|Y|, n, q) = (243, 11, 3)$, or
# 3. $(|Y|, n, q) = (9a^2 (9a^2-1)/2, (9a^2+1)/5, 6)$, where $a \equiv 21, 69 \pmod{240}$.
# 
# 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.
# 
# [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$.

# In[1]:


import drg


# A scheme with the above Krein array would have $r^2 (r^2 - 1)/2$ vertices.

# In[2]:


r, t = var("r t")
p = drg.QPolyParameters([r^2 - 4, r^2 - 9, 10, 1], [1, 2, r^2 - 9, r^2 - 4])
p.order(factor = True, simplify = True)


# 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.

# In[3]:


p.kreinParameters(factor = True, simplify = True)


# The intersection numbers can be checked to be nonnegative and integral for odd values of $r \ge 5$.

# In[4]:


p.pTable(factor = True, simplify = True)


# 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.

# In[5]:


S111 = p.tripleEquations(1, 1, 1, params={'A': (1, 2, 3)})
S111[1, 1, 1]


# The above triple intersection number is integral for odd values of $r$ whenever $5r + 4 - 9/r$ is divisible by $8$.

# In[6]:


(S111[1, 1, 1] + (5*r + 4 - 9/r)/8).subs(r == 2*t + 1).factor()


# 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.
# 
# 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.