Return to Answer

This is an attempt to understand the very nice argument by Peter Mueller (completed by OP, Sean Eberhard, in the comments). I am not completely happy with it, and would like to encourage others to look for more conceptual explanations.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

It may be proved by straightforward calculations, but let me give an argument if not conceptual, but at least almost calculations-free.

First of all, we use the following characterization of $PSL(2,q)$ (probably well known, but I did not see it before.)

Lemma. A projective transformation $s(x)=\frac{ax+b}{cx+d}, c\ne 0$, belongs to $PSL(2,q)$ if and only if the equation $s'(x)=1$ has two roots in $\mathbb{F}_q$.

Proof. Note that both properties are preserved when we replace $s(x)$ to $s(x)+C$ and $s(x+C)$ for constant $C\in \mathbb{F}_q$. So we may suppose that $a=0$ (subtract constant $a/c$ from $s(x)$) and also that $d=0$ (replace $s(x)$ by $s(x-d/c)$). So $s(x)=M/x$ for some constant $M$, and both conditions say that $-M$ is a non-zero square.

Next observation concerns the discriminants of the quadratic equation and critical values of corresponding functions. For the equation $f(x)=-x^2+2ax+b=0$, we all know that its discriminant $a^2-b$ equals $f(x_0)$, where $x_0=a$ is the critical value. But we deal with a slightly different equation $h(x):=s(x)-x=0$. After shifting the variable we get a function of the form $h_0(x)=-A/x+B-x$. Its discriminant is $D=B^2-4A$, and the critical values are $x_1=\sqrt{A},x_2=-\sqrt{A}$, so in our situation $A$ is a square by Lemma. Also we get $$D=h_0(x_1)h_0(x_2).$$

Since $h(x)=s(x)-x$ does not have roots, $D$ is not a square. Thus exactly one of two values of $h$ at critical points is a square. This value is the unique appropriate $\alpha$, as desired.

This is an attempt to understand the very nice argument by Peter Mueller (completed by OP, Sean Eberhard, in the comments). I am not completely happy with it, and would like to encourage others to look for more conceptual explanations.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

It may be proved by straightforward calculations, but let me give an argument if not conceptual, but at least almost calculations-free.

First of all, we use the following characterization of $PSL(2,q)$ (probably well known, but I did not see it before.)

Lemma. A projective transformation $s(x)=\frac{ax+b}{cx+d}, c\ne 0$, belongs to $PSL(2,q)$ if and only if the equation $s'(x)=1$ has two roots in $\mathbb{F}_q$.

Proof. Note that both properties are preserved when we replace $s(x)$ to $s(x)+C$ and $s(x+C)$ for constant $C\in \mathbb{F}_q$. So we may suppose that $a=0$ (subtract constant $a/c$ from $s(x)$) and also that $d=0$ (replace $s(x)$ by $s(x-d/c)$). So $s(x)=M/x$ for some constant $M$, and both conditions say that $-M$ is a non-zero square.

Next observation concerns the discriminants of the quadratic equation and critical values of corresponding functions. For the equation $f(x)=-x^2+2ax-b=0$, we all know that its discriminant $a^2-b$ equals $f(x_0)$, where $x_0=a$ is the critical value. But we deal with a slightly different equation $h(x):=s(x)-x=0$. After shifting the variable we get a function of the form $h_0(x)=-A/x+B-x$. Its discriminant is $D=B^2-4A$, and the critical values are $x_1=\sqrt{A},x_2=-\sqrt{A}$, so in our situation $A$ is a square by Lemma. Also we get $$D=h_0(x_1)h_0(x_2).$$

Since $h(x)=s(x)-x$ does not have roots, $D$ is not a square. Thus exactly one of two values of $h$ at critical points is a square. This value is the unique appropriate $\alpha$, as desired.

This is an attempt to understand the very nice argument by Peter Mueller (completed by OP, Sean Eberhard, in the comments). I am not completely happy with it, and would like to encourage others to look for more conceptual explanations.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

It may be proved by straightforward calculations, but let me give an argument if not conceptual, but at least almost calculations-free.

First of all, we use the following characterization of $PSL(2,q)$ (probably well known, but I did not see it before.)

Lemma. A projective transformation $s(x)=\frac{ax+b}{cx+d}, c\ne 0$, belongs to $PSL(2,q)$ if and only if the equation $s'(x)=1$ has two roots in $\mathbb{F}_q$.

Proof. Note that both properties are preserved when we replace $s(x)$ to $s(x)+C$ and $s(x+C)$ for constant $C\in \mathbb{F}_q$. So we may suppose that $a=0$ (subtract constant $a/c$ from $s(x)$) and also that $d=0$ (replace $s(x)$ by $s(x-d/c)$). So $s(x)=M/x$ for some constant $M$, and both conditions say that $-M$ is a non-zero square.

Next observation concerns the discriminants of the quadratic equation and critical values of corresponding functions. For the equation $f(x)=-x^2+2ax+b=0$, we all know that its discriminant $a^2-b$ equals $f(x_0)$, where $x_0=a$ is the critical value. But we deal with a slightly different equation $h(x):=s(x)-x=0$. After shifting the variable we get a function of the form $h_0(x)=-A/x+B-x$. Its discriminant is $D=B^2-4A$, and the critical values are $x_1=\sqrt{A},x_2=-\sqrt{A}$, so in our situation $A$ is a square by Lemma. Also we get $$D=h_0(x_1)h_0(x_2).$$

Since $h(x)=s(x)-x$ does not have fixed points, $D$ is not a square. Thus exactly one of two values of $h$ at critical points is a square. This value is the unique appropriate $\alpha$, as desired.

This is an attempt to understand the very nice argument by Peter Mueller (completed by OP, Sean Eberhard, in the comments). I am not completely happy with it, and would like to encourage others to look for more conceptual explanations.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

It may be proved by straightforward calculations, but let me give an argument if not conceptual, but at least almost calculations-free.

First of all, we use the following characterization of $PSL(2,q)$ (probably well known, but I did not see it before.)

Lemma. A projective transformation $s(x)=\frac{ax+b}{cx+d}, c\ne 0$, belongs to $PSL(2,q)$ if and only if the equation $s'(x)=1$ has two roots in $\mathbb{F}_q$.

Proof. Note that both properties are preserved when we replace $s(x)$ to $s(x)+C$ and $s(x+C)$ for constant $C\in \mathbb{F}_q$. So we may suppose that $a=0$ (subtract constant $a/c$ from $s(x)$) and also that $d=0$ (replace $s(x)$ by $s(x-d/c)$). So $s(x)=M/x$ for some constant $M$, and both conditions say that $-M$ is a non-zero square.

Next observation concerns the discriminants of the quadratic equation and critical values of corresponding functions. For the equation $f(x)=-x^2+2ax+b=0$, we all know that its discriminant $a^2-b$ equals $f(x_0)$, where $x_0=a$ is the critical value. But we deal with a slightly different equation $h(x):=s(x)-x=0$. After shifting the variable we get a function of the form $h_0(x)=-A/x+B-x$. Its discriminant is $D=B^2-4A$, and the critical values are $x_1=\sqrt{A},x_2=-\sqrt{A}$, so in our situation $A$ is a square by Lemma. Also we get $$D=h_0(x_1)h_0(x_2).$$

Since $h(x)=s(x)-x$ does not have roots, $D$ is not a square. Thus exactly one of two values of $h$ at critical points is a square. This value is the unique appropriate $\alpha$, as desired.

This is to complete the very nice argument by Peter Mueller.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

Possibly this have some clever explanation, but at the moment I do not see it, so just calculate.

Denote $s(x)=(ax+b)/(cx+d)$, $ad-bc=1$. Since $s$ does not have a fixed point, we have $c\ne 0$ (else $\infty$ would be a fixed point) and the discriminant $$(d-a)^2+4bc=(d+a)^2-4=(d+a-2)(d+a+2)$$ of the equation $ax+b-x(cx+d)=0$ is not a square. Therefore one of the numbers $d+a-2,d+a+2$ is a quadratic residue and the other is not. Equation (1) simplifies as $$ (ax+b)-(cx+d)(x+\alpha)=-cx^2+x((a-d)-c\alpha)+b-d\alpha, $$ thus it has a double root when the discriminant is zero: $$ (a-d-c\alpha)^2+4c(b-d\alpha)=(\alpha c-(a+d))^2-4(ad-bc)=(\alpha c-(a+d+2))(\alpha c-(a+d-2))=0 $$ This happens for $\alpha=c^{-1}(a+d\pm 2)$, and exactly for one choice of the sign $\alpha$ appears to be a quadratic residue.

This is an attempt to understand the very nice argument by Peter Mueller (completed by OP, Sean Eberhard, in the comments). I am not completely happy with it, and would like to encourage others to look for more conceptual explanations.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

It may be proved by straightforward calculations, but let me give an argument if not conceptual, but at least almost calculations-free.

First of all, we use the following characterization of $PSL(2,q)$ (probably well known, but I did not see it before.)

Lemma. A projective transformation $s(x)=\frac{ax+b}{cx+d}, c\ne 0$, belongs to $PSL(2,q)$ if and only if the equation $s'(x)=1$ has two roots in $\mathbb{F}_q$.

Proof. Note that both properties are preserved when we replace $s(x)$ to $s(x)+C$ and $s(x+C)$ for constant $C\in \mathbb{F}_q$. So we may suppose that $a=0$ (subtract constant $a/c$ from $s(x)$) and also that $d=0$ (replace $s(x)$ by $s(x-d/c)$). So $s(x)=M/x$ for some constant $M$, and both conditions say that $-M$ is a non-zero square.

Next observation concerns the discriminants of the quadratic equation and critical values of corresponding functions. For the equation $f(x)=-x^2+2ax+b=0$, we all know that its discriminant $a^2-b$ equals $f(x_0)$, where $x_0=a$ is the critical value. But we deal with a slightly different equation $h(x):=s(x)-x=0$. After shifting the variable we get a function of the form $h_0(x)=-A/x+B-x$. Its discriminant is $D=B^2-4A$, and the critical values are $x_1=\sqrt{A},x_2=-\sqrt{A}$, so in our situation $A$ is a square by Lemma. Also we get $$D=h_0(x_1)h_0(x_2).$$

Since $h(x)=s(x)-x$ does not have fixed points, $D$ is not a square. Thus exactly one of two values of $h$ at critical points is a square. This value is the unique appropriate $\alpha$, as desired.