Paleyグラフ

有限体 の定理「有限体の乗法群の構造」により $\mathbb F_q^\times$ は位数 $q-1$ の巡回群なので、生成元 $\gamma$ をとる。$q-1$ は偶数なので、$\gamma^j$ が平方元であることと $j$ が偶数であることは同値である（$\gamma^j=\gamma^{2i}$ なら $j\equiv2i\pmod{q-1}$ で $j$ は偶数）。
1：$j=0,1,\dots,q-2$ のうち偶数と奇数は $\frac{q-1}2$ 個ずつである。$y^2=a$ の解は $y$ と $-y$ で、$q$ が奇数なので $y\neq-y$ であり、2 次方程式の解は高々 2 個なので、これで全部である。
2：$Q=\{\gamma^{2i}\}$ は部分群で、指数は $2$ である。$n=\gamma^{j}$（$j$ は奇数）をかけると指数の偶奇が入れ替わるので、$nQ=N$、$nN=Q$ である。
3：$-1$ は $\mathbb F_q^\times$ のただ 1 つの位数 $2$ の元なので $-1=\gamma^{(q-1)/2}$ であり、$-1\in Q$ は $\frac{q-1}2$ が偶数、すなわち $q\equiv1\pmod4$ と同値である。$\square$

1：$x$ に隣接する頂点は $x+s$（$s\in Q$）なので、$\lvert Q\rvert=\frac{q-1}2$ 個である。
2：$(ax+b)-(ay+b)=a(x-y)$ であり、lem-paley-squares の 2 から、$a\in Q$ なら $a(x-y)\in Q$ と $x-y\in Q$ は同値である。$x\mapsto ax+b$ は全単射なので自己同型である。
3：同じく 2 から、$n\in N$ なら $n(x-y)\in Q$ と $x-y\in N$ は同値であり、$x\neq y$ のとき $x-y\in N$ は「$P_q$ で隣接しない」ことと同値である。
4：$a:=(y'-x')(y-x)^{-1}$、$b:=x'-ax$ とおくと、$x\mapsto ax+b$ は $x$ を $x'$ に、$y$ を $y'$ に写す。$(x,y)$ と $(x',y')$ がともに隣接する対なら $y-x,y'-x'\in Q$ なので、ともに隣接しない対なら $y-x,y'-x'\in N$ なので、どちらの場合も 2 から $a\in Q$ である（$Q$ は部分群なので、$N$ の元の逆元は $N$ に属する）。2 によりこれは自己同型である。$\square$

$c=0$ なら各項が $1$ である。$c\neq0$ なら $x\mapsto cx$ は全単射なので、和は $s:=\sum_y\psi(y)$ に等しい。$\psi(y_0)\neq1$ となる $y_0$ をとると、$y\mapsto y+y_0$ も全単射なので $s=\sum_y\psi(y+y_0)=\psi(y_0)s$ であり、$s=0$ である。$\lvert\psi(x)\rvert=1$ から $\overline{\psi(x)}=\psi(-x)$ なので、$\sum_xv_a(x)\overline{v_b(x)}=\sum_x\psi((a-b)x)=0$ である。0 でない直交するベクトルが $q$ 個あるので、基底である。$\square$

1（固有ベクトル）。 $x$ に隣接する頂点は $x+s$（$s\in Q$）なので
$$ (Av_a)(x)=\sum_{s\in Q}\psi(a(x+s))=\psi(ax)\sum_{s\in Q}\psi(as)=\theta_a\,v_a(x),\qquad\theta_a:=\sum_{s\in Q}\psi(as) $$
である。$\theta_0=\lvert Q\rvert=\frac{q-1}2$ である。lem-paley-squares の 1 により各 $s\in Q$ は $\mathbb F_q^\times$ のちょうど 2 元の平方なので、$\sum_{x\neq0}\psi(ax^2)=2\theta_a$ であり、$x=0$ の項 $1$ を加えて $g(a)=1+2\theta_a$ である。
2（絶対値と実数性）。 $a\neq0$ とする。$\overline{\psi(ay^2)}=\psi(-ay^2)$ なので
$$ \lvert g(a)\rvert^2=\sum_{x,y\in\mathbb F_q}\psi\bigl(a(x^2-y^2)\bigr)=\sum_{x,y}\psi\bigl(a(x-y)(x+y)\bigr) $$
である。$q$ は奇数なので $2$ は $\mathbb F_q$ で可逆であり、$(x,y)\mapsto(u,w):=(x-y,x+y)$ は $\mathbb F_q^2$ の全単射である。よって lem-paley-orthogonal により
$$ \lvert g(a)\rvert^2=\sum_{u}\sum_{w}\psi(auw)=\sum_u\begin{cases}q&(au=0)\\0&(au\neq0)\end{cases}=q $$
である。次に、$-1\in Q$ なので $-1=\iota^2$ となる $\iota\in\mathbb F_q$ がある。$x\mapsto\iota x$ は全単射なので
$$ \overline{g(a)}=\sum_x\psi(-ax^2)=\sum_x\psi\bigl(a(\iota x)^2\bigr)=g(a) $$
であり、$g(a)$ は実数である。$g(a)^2=\lvert g(a)\rvert^2=q$ を得る。
3（符号の個数）。 $c=z^2\in Q$ なら、$x\mapsto zx$ が全単射なので $g(ac)=g(a)$ である。$n\in N$ をとる。1 の計算と lem-paley-squares の 2（$nQ=N$）から
$$ g(a)+g(an)=2+2\sum_{s\in Q}\psi(as)+2\sum_{t\in N}\psi(at)=2+2\sum_{x\neq0}\psi(ax)=2+2(0-1)=0 $$
である（lem-paley-orthogonal）。よって $g$ は $Q$ の上で一定の値 $g(1)$ をとり、$N$ の上で $-g(1)$ をとる。$\lvert Q\rvert=\lvert N\rvert=\frac{q-1}2$ から 3 が従う。
最後に、lem-paley-orthogonal により $v_a$ は基底なので、1〜3 から固有値とその重複度が上のとおりに定まる。$\square$

$J$ をすべての成分が $1$ の行列、$I$ を単位行列とする。$\theta=\frac{-1\pm\sqrt q}2$ は $\theta^2+\theta-t=0$ を満たす（$\theta^2+\theta=\frac{q-1}4=t$）。$B:=A^2+A-tI-tJ$ とおく。$a\neq0$ なら $v_a$ は $\mathbf 1=v_0$ と直交するので $Jv_a=0$ であり、thm-paley-spectrum により $Av_a=\theta v_a$（$\theta$ は $\frac{-1\pm\sqrt q}2$ のどちらか）なので $Bv_a=(\theta^2+\theta-t)v_a=0$ である。$v_0=\mathbf 1$ については $Jv_0=qv_0$ から
$$ Bv_0=\bigl((2t)^2+2t-t-tq\bigr)v_0=\bigl(4t^2+t-t(4t+1)\bigr)v_0=0 $$
である。基底を $0$ に写すので $B=0$、すなわち
$$ A^2=tI-A+tJ=2t\,I+(t-1)A+t\,(J-I-A) $$
である。$A^2$ の $(x,y)$ 成分は $x,y$ の共通の隣接頂点の個数なので、対角成分から $k=2t$、隣接する対で $t-1$、隣接しない相異なる対で $t$ を得る。$P_q$ は $Q$ と $N$ がともに空でないので完全グラフでも辺のないグラフでもない。$\mu=t\ge1$ なので、隣接しない 2 頂点には共通の隣接頂点があり、連結で直径は $2$ である。$\square$

$K$ をクリークとし、$n\in N$ をとる。写像 $K\times K\to\mathbb F_q$、$(x,y)\mapsto x+ny$ が単射であることを示す。$x+ny=x'+ny'$ とすると $x-x'=n(y'-y)$ である。$y\neq y'$ なら、$K$ がクリークなので $y'-y\in Q$ であり、右辺は $nQ=N$ に属する（lem-paley-squares の 2）。左辺は $x=x'$ なら $0$、$x\neq x'$ なら $Q$ に属するので、どちらにしても右辺と等しくない。よって $y=y'$ であり、$x=x'$ である。したがって $\lvert K\rvert^2\le q$ である。独立集合 $L$ については、prop-paley-basic の 3 により $x\mapsto nx$ が $L$ をクリークに写すので、同じ評価が成り立つ。$\square$

$Q=\{1,2,4,8,9,13,15,16\}$ である。$4$ 頂点のクリーク $K$ があるとし、その 2 頂点 $x,y$ をとる。prop-paley-basic の 4 により、$(x,y)$ を $(0,1)$ に写す自己同型があるので、$0,1\in K$ としてよい。$K$ の残りの 2 頂点は $0$ と $1$ の両方に隣接する。$z$ が $0$ と $1$ の両方に隣接するのは $z\in Q$ かつ $z-1\in Q$ のときで、$Q$ の元を順に調べると $z=2,9,16$ だけである（$z-1=1,8,15$）。ところが $9-2=7$、$16-2=14$、$16-9=7$ はどれも $Q$ に属さないので、この 3 頂点のどの 2 つも隣接しない。これは $K$ がクリークであることに反する。一方 $\{0,1,2\}$ は差が $1,2,1\in Q$ なので 3 頂点のクリークであり、クリークの最大の大きさは $3$ である。独立集合は、$3\in N$ による $x\mapsto3x$ でクリークに写る（prop-paley-basic の 3）ので、$4$ 頂点の独立集合もない。
よって $K_{17}$ の辺を、$P_{17}$ の辺を赤、それ以外を青に塗ると、単色の $K_4$ がなく、$R(4,4)>17$ である。一方、Ramseyの定理 の命題「3 と 4 の Ramsey 数」により $R(3,4)=9$、命題「Ramsey 数の基本性質」により $R(4,3)=9$ であり、補題「Ramsey 数の漸化不等式」から $R(4,4)\le R(3,4)+R(4,3)=18$ である。$\square$

thm-paley-spectrum により、$P_q$ は $d=\frac{q-1}2$ 正則で、$d$ の重複度は $1$、$\lambda(P_q)=\frac{\sqrt q+1}2$ である。エクスパンダーグラフ の定理「エクスパンダー混合補題」の右側の不等式 $\bigl\lvert e(S,T)-\frac{d\lvert S\rvert\lvert T\rvert}{q}\bigr\rvert\le\lambda(P_q)\sqrt{\lvert S\rvert\lvert T\rvert}$ に代入すればよい。$\square$

$x\neq y$ なら $y-x\in\mathbb F_q^\times$ で、lem-paley-squares の 3 により $-1\in N$ なので、2 から $y-x\in Q$ と $x-y=(-1)(y-x)\in Q$ のちょうど一方が成り立つ。よって相異なる 2 頂点の間には、ちょうど 1 本の向きの付いた辺がある。$x$ から出る辺の行き先は $x+s$（$s\in Q$）で、$\frac{q-1}2$ 個である。$\square$