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

# # Nonexistence of a distance-regular graph with intersection array $\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\}$
# 
# We will show that a distance-regular graph with intersection array $\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\}$, where $r, t \ge 1$, does not exist. The intersection array arises for graphs of diameter $3$ with $b_2 = c_2$ and $p^3_{33}$ even which are $Q$-polynomial with respect to the natural ordering of eigenvalues and contain a maximal $1$-code that is both locally regular and last subconstituent perfect. See [Extremal $1$-codes in distance-regular graphs of diameter $3$](http://link.springer.com/article/10.1007/s10623-012-9651-0) by A. Jurišić and J. Vidali, where the theory for dealing with such intersection arrays has been developed.

# In[1]:


import drg


# This family is not entirely feasible, however, we will find two infinite feasible subfamilies.

# In[2]:


r, t = var("r t")
p = drg.DRGParameters([(2*r+1)*(4*r+1)*(4*t-1), 8*r*(4*r*t-r+2*t), (r+t)*(4*r+1)],
     [1, (r+t)*(4*r+1), 4*r*(2*r+1)*(4*t-1)])
p.order(expand = True, factor = True)


# The two feasible subfamilies can be obtained by setting $t = 4r^2$ and $t = 2r(2r+1)$, respectively.

# In[3]:


pa = p.subs(t == 4*r^2)
print(pa)
print(pa.order(expand = True, factor = True))


# In[4]:


pb = p.subs(t == 2*r*(2*r+1))
print(pb)
print(pb.order(expand = True, factor = True))


# Let us check that the first members of each family are indeed feasible. We skip the family nonexistence check since the intersection array of the entire family is already included.

# In[5]:


pa1 = pa.subs(r == 1)
print(pa1)
print(pa1.order())
pa1.check_feasible(skip = ["family"])


# In[6]:


pb1 = pb.subs(r == 1)
print(pb1)
print(pb1.order())
pb1.check_feasible(skip = ["family"])


# We now compute the Krein parameters. We have $q^1_{13} = q^1_{31} = q^3_{11} = 0$, so the graph would be $Q$-polynomial with respect to the natural ordering of the eigenvalues.

# In[7]:


p.set_vars([t, r])
p.kreinParameters()
[p.q[1, 1, 3], p.q[1, 3, 1], p.q[3, 1, 1]]


# We now compute the triple intersection numbers with respect to three vertices $u, v, w$ at mutual distances $3$. Let us first check that $p^3_{33}$ is positive.

# In[8]:


p.p[3, 3, 3].expand().factor()


# The parameter $a$ will denote the number of vertices at distance $3$ from all of $u, v, w$. Let us count the number of vertices at distance $1$ or $2$ from one of $u, v, w$ and $3$ from the other two vertices.

# In[9]:


S333 = p.tripleEquations(3, 3, 3, params = {"a": (3, 3, 3)})
[S333[s].expand().factor() for s in [(1, 3, 3), (3, 1, 3), (3, 3, 1), (2, 3, 3), (3, 2, 3), (3, 3, 2)]]


# Note that for the above expressions to be nonnegative, we must have $a = 4r - 1$, and then they are all equal to zero. Consequently, all of the $a_3$ vertices adjacent to one of $u, v, w$ which are at distance $3$ from another of these vertices are at distance $2$ from the remaining vertex in the triple.

# In[10]:


a = S333[3, 3, 3]
S333a = S333.subs(a == 4*r - 1)
print(p.a[3].expand().factor())
[S333a[s].expand().factor() for s in [(1, 2, 3), (3, 1, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (1, 3, 2)]]


# The above results mean that any two vertices $v, w$ at distance $3$ uniquely define a set $C$ of $4r + 2$ vertices mutually at distance $3$ containing $v, w$ - i.e., a $1$-code in the graph. Furthermore, since $a_3$ is nonzero, for each $u$ in $C \setminus \{v, w\}$, there are vertices at distances $3, 1, 2$ from $u, v, w$. We now check that $c_3 = a_3 p^3_{33}$.

# In[11]:


print(p.c[3].expand().factor())
print((p.a[3] * p.p[3, 3, 3]).expand().factor())


# Let $u'$ be a neighbour of $v$. Since $u'$ is not in $C$, it may be at distance $3$ from at most one vertex of $C$. As there are $c_3$ and $a_3$ neighbours of $v$ that are at distances $2$ and $3$ from $w$, respectively, the above equality implies that each neighbour of $v$ is at distance $3$ from precisely one vertex of $C$.
# 
# Suppose now that $u'$ is at distance 2 from $w$. Let us count the number of vertices at distances $1, 1, 3$ from $u', v, w$.

# In[12]:


S123 = p.tripleEquations(1, 2, 3, params = {"b": (3, 3, 3)})
b = S123[3, 3, 3]
S123b = S123.subs(b == 1)
S123b[1, 1, 3]


# As this value is nonintegral, we conclude that a graph with intersection array $\{(2r+1)(4r+1)(4t-1), 8r(4rt-r+2t), (r+t)(4r+1); 1, (r+t)(4r+1), 4r(2r+1)(4t-1)\}$ and $r, t \ge 1$ **does not exist**.