# An improved point-line incidence bound over arbitrary finite fields via the
VC-dimension theory

Alex Iosevich Department of Mathematics, University of Rochester.
<EMAIL_ADDRESS>Thang Pham University of Science, Vietnam
National University, Hanoi. Email<EMAIL_ADDRESS>Steven Senger
Department of Mathematics, Missouri State University. Email:
<EMAIL_ADDRESS>Michael Tait Department of Mathematics and
Statistics, Villanova University. Email<EMAIL_ADDRESS>
###### Abstract

The main purpose of this paper is to prove that the point-line incidence bound
due to Vinh (2011) over arbitrary finite fields can be improved in certain
ranges by using tools from the VC-dimension theory. As consequences, a number
of applications will be discussed in detail.

##  1 Introduction

Let $\mathbb{F}_{q}$ be a finite field of order $q$, where $q$ is a prime
power. Let $P$ be a set of points in $\mathbb{F}_{q}^{2}$ and $L$ be a set of
lines in $\mathbb{F}_{q}^{2}$. The number of incidences between $P$ and $L$ is
denoted by $I(P,L)$. We use the notation $f\ll g$ to mean that $f=O(g)$.

The following point-line incidence bound is due to Vinh [18], which was proved
by using the spectral graph theory method.

######  Theorem 1.1.

The number of incidences between $P$ and $L$ satisfies

$\left|I(P,L)-\frac{|P||L|}{q}\right|\ll q^{\frac{1}{2}}\sqrt{|P||L|}.$ (1)

To see how good this theorem is, we compare to the well-known Cauchy-Schwarz
estimates.

$I(P,L)\leq\min\\{|P|^{1/2}|L|+|P|,~{}|P||L|^{1/2}+|L|\\}.$ (2)

More precisely,

  1. 1.

If $q^{3}=o(|P|L|)$, Theorem 1.1 offers the sharp bound
$I(P,L)=(1+o(1))|P||L|/q$.

  2. 2.

If $|P|>q$ and $|L|>q$, then the bound (1) is better than those in (2).

  3. 3.

When $|P|<q$ or $|L|<q$ and $|P|\neq|L|$, there is no non-trivial bound in the
literature.

Although there are a number of elementary proofs for the above theorem, for
instance, Cilleruelo’s proof using Sidon sets in [2] or a geometric counting
argument due to Murphy and Petridis in [10], it is very difficult to say under
what conditions the theorem will be improved in the general setting of
arbitrary finite fields and what methods will be suitable for this purpose.

In the setting of prime fields, there exists a number of better results in the
literature. The first paper was written by Bourgain, Katz and Tao [1] in 2004,
in which they proved that for any point set $\mathcal{P}$ and any line set
$\mathcal{L}$ in $\mathbb{F}_{p}^{2}$ with
$|\mathcal{P}|=|\mathcal{L}|=N=p^{\alpha}$, $0<\alpha<2$, we have

$I(\mathcal{P},\mathcal{L})\ll N^{\frac{3}{2}-\varepsilon},$ (3)

where $\varepsilon$ is positive and depends on $\alpha$. The exponent
$\varepsilon$ has been made explicit over the years, and the most recent
progress is due to Stevens and de Zeeuw [17], who showed
$I(P,L)\ll|P|^{11/15}|L|^{11/15}$ under a certain conditions on the sizes of
$P$ and $L$. This improves earlier results due to Helfgott and Rudnev [4] and
Jones [8]. While the methods in [4, 8] rely on a pivoting argument and sum-
product type problems, the main ingredient in Stevens and De Zeeuw’s proof is
a point-plane incidence bound due to Rudnev [13]. If we assume to have some
additional conditions on the energy of the sets, then some improvements can be
obtained, see [12, 14]. We also note that the Stevens-De Zeeuw’s result also
holds over arbitrary fields, but the bounds obtained are in terms of the
characteristic of the field so the sets where the bound is good may be small
compared to $q$ if $q$ is not prime. Jones [7] proved that the argument in [4,
8] can be used to derive a result of the form (3) when $|P|=|L|=N$ over
arbitrary finite fields as long as the intersection of the point set $P$ and
translations of all subfields satisfies some additional conditions.

The main purpose of this paper is to show that tools from the VC-dimension
theory can be used to prove an improved point-line incidence bound over
$\mathbb{F}_{q}$. A number of applications will also be discussed.

###  1.1 Statement of results

######  Theorem 1.2.

Let $L$ be a set of lines in $\mathbb{F}_{q}^{2}$ of the form $y=ax+b$ with
$a\neq 0$ and $P=A\times B\subset\mathbb{F}_{q}^{2}$. Assume that
$|L||A|>q^{\alpha}\max\\{|A|,|L_{x}|\\}$ for some $\alpha\in(0,1)$, then

$I(A\times
B,L)\ll\frac{|L||A||B|^{1/2}}{q^{\alpha/2}}+q^{\alpha}|L|^{1/2}|A|^{1/2}|B|^{1/2}.$

Here $L_{x}:=\\{a\colon y=ax+b\in L\\}$. In addition, if $L$ also contains
lines of the from $y=c$ or $x=c$, then

$I(A\times
B,L)\ll\frac{|L||A||B|^{1/2}}{q^{\alpha/2}}+q^{\alpha}|L|^{1/2}|A|^{1/2}|B|^{1/2}+2|A||B|.$

The key ingredient in the proof of this theorem is a point-plane incidence
theorem in $\mathbb{F}_{q}^{3}$, which will be proved by using tools from VC
dimension theory. In this paper, we present two versions, where the main
difference comes from either the maximal number of collinear points or
collinear planes.

######  Theorem 1.3.

Let $P$ be a set of points and $\Pi$ be a set of planes in
$\mathbb{F}_{q}^{3}$. Assume planes in $\Pi$ are of the form $a\cdot x=1$ with
$a\in\mathbb{F}_{q}^{3}$. If $|\Pi|\geq 2q^{1+\alpha}$ for some
$\alpha\in(0,1)$, then

$I(P,\Pi)\ll\frac{|P||\Pi|}{q^{\alpha}}+|\Pi|q^{2\alpha}.$

Symmetrically, if $|P|\geq 2q^{1+\alpha}$ for some $\alpha\in(0,1)$, then

$I(P,\Pi)\ll\frac{|P||\Pi|}{q^{\alpha}}+|P|q^{2\alpha}.$

If we relax the condition $|P|\geq 2q^{1+\alpha}$ to $|P|\geq 2kq^{\alpha}$,
where $k$ is the maximal number of collinear points in $P$, then we have the
next theorem.

######  Theorem 1.4.

Let $P$ be a set of points and $\Pi$ be a set of planes in
$\mathbb{F}_{q}^{3}$. Assume planes in $\Pi$ are of the form $a\cdot x=1$ with
$a\in\mathbb{F}_{q}^{3}$. If there is no line that contains $k$ points from
$P$ and is contained in two planes in $\Pi$, and $|P|\geq 2kq^{\alpha}$, then

$I(P,\Pi)\ll\frac{|P||\Pi|}{q^{\alpha}}+|P|q^{2\alpha}.$

###  1.2 Applications

We now discuss some more applications which might be of independent interest.

#### Intersection of planes in $\mathbb{F}_{q}^{3}$:

The next theorem tells us that given $U^{\prime}\subset U$ with
$|U^{\prime}|^{3}\ll|U|^{2}$, then there are many pairs $(u,v)\in U\times U$
such that the corresponding planes have the same intersection with
$U^{\prime}$, namely, $\pi_{u}\cap U^{\prime}=\pi_{v}\cap U^{\prime}.$

The formal statement reads as follows.

######  Theorem 1.5.

Given $U\subset\mathbb{F}_{q}^{3}$ with $|U|\gg q^{2}$, and $U^{\prime}\subset
U$ with $|U^{\prime}|^{3}\ll|U|^{2}$, then the number of pairs $(u,v)\in
U^{2}$ such that $\pi_{u}\cap U^{\prime}=\pi_{v}\cap U^{\prime}$ is at least
$|U|^{2}/|U^{\prime}|^{3}$.

#### Distances between two sets in $\mathbb{F}_{q}^{3}$:

Given $E,F\subset\mathbb{F}_{q}^{3}$, the distance set between $E$ and $F$ is
denoted by $\Delta(E,F)$, which is

$\Delta(E,F)=\\{||x-y||=(x_{1}-y_{1})^{2}+(x_{2}-y_{2})^{2}+(x_{3}-y_{3})^{2}\colon
x\in E,y\in F\\}\subset\mathbb{F}_{q}.$

When the sizes of $E$ and $F$ are very different, the best current result over
arbitrary finite fields is due to Koh and Sun in [9]. In particular, they
proved that

$|\Delta(E,F)|\gg\begin{cases}\min\\{q,|E||F|q^{-(d-1)}\\}~{}~{}&\mbox{if}~{}|E|<q^{\frac{d-1}{2}}\\\
\min\\{q,|F|q^{-\frac{d-1}{2}}\\}~{}~{}&\mbox{if}~{}q^{\frac{d-1}{2}}\leq|E|\leq
q^{\frac{d+1}{2}}\\\ \min\\{q,|E||F|q^{-d}\\}~{}~{}&\mbox{if}~{}|E|\geq
q^{\frac{d+1}{2}}\end{cases}.$ (4)

Note that in even dimensions, we need an additional condition that $|E||F|\gg
q^{d}$.

In the next theorem, we improve this result in certain ranges in
$\mathbb{F}_{q}^{3}$.

######  Theorem 1.6.

Let $E$ and $F$ be sets in $\mathbb{F}_{q}^{3}$ with $q\equiv 3\mod 4$. Assume
that the number of pairs of distance zero is at most $|E||F|/2$. Define $k$ to
be the maximum integer such that there are $k$ collinear points in $F$
$\\{u_{1},\cdots,u_{k}\\}$ with the property that there is a pair of points
$(x,y)\in E\times E$ satisfying $||x-u_{i}||=||y-u_{i}||\neq 0$ for all $i$.
Define $\alpha$ by $|F|>2kq^{\alpha}$. For $\alpha\in(0,1)$, we have

$|\Delta(E,F)|\gg\begin{cases}\max\\{k,~{}q^{\alpha}\\}~{}~{}~{}&\mbox{if}~{}|E|\geq
q^{3\alpha}\\\
\max\left\\{k,\frac{|E|}{q^{2\alpha}}\right\\}~{}~{}~{}&\mbox{if}~{}|E|\leq
q^{3\alpha}\end{cases}$

We refer the reader to [5, 11, 16] for results when the sets $E$ and $F$ are
the same.

#### Dot product between two sets in $\mathbb{F}_{q}^{3}$:

Given $E,F\subset\mathbb{F}_{q}^{3}$, the dot-product set between $E$ and $F$
is denoted by $D(E,F)$, which is

$D(E,F)=\\{x\cdot y\colon x\in E,y\in F\\}\subset\mathbb{F}_{q}.$

Similarly, we have the following variant of Theorem 1.6 for the dot-product
function.

######  Theorem 1.7.

Let $E$ and $F$ be sets in $\mathbb{F}_{q}^{3}$. Assume that the number of
orthogonal pairs in $E\times F$ is at most $|E||F|/2$, and any two planes of
the form $v\cdot x=\lambda$ and $w\cdot x=\lambda$, $v,w\in E$, $\lambda\neq
0$, have at most $k$ collinear points in common from $F$. Assume in addition
that $|F|>2kq^{\alpha}$ and $E$ is not contained fully in any plane, then

$|D(E,F)|\gg\begin{cases}\max\\{k,~{}q^{\alpha}\\}~{}~{}~{}&\mbox{if}~{}|E|\geq
q^{3\alpha}\\\
\max\left\\{k,\frac{|E|}{q^{2\alpha}}\right\\}~{}~{}~{}&\mbox{if}~{}|E|\leq
q^{3\alpha}\end{cases}.$

###  1.3 Improved ranges of results

#### Improved ranges of Theorem 1.2:

Theorem 1.2 performs well when the sizes of the point and line sets are far
apart. Relatively less is known about this case compared to the case where the
number of points and lines are close together, see for example the discussion
in [19]. Theorem 1.2 offers a better upper bound in its domain compared to
those in (1) and (2) in the range

  1. 1.

If $|L||A|<q^{3\alpha}$, then Theorem 1.2 gives
$q^{\alpha}|L|^{1/2}|A|^{1/2}|B|^{1/2}$. This is better than (1) and (2) in
the range

$\alpha<1/2,~{}q^{\alpha}\max\\{|A|,|L_{x}|\\}<|L||A|<q^{3\alpha},|L|>q^{2\alpha},~{}|A||B|>|L|q^{2\alpha}.$

  2. 2.

If $|L||A|>q^{3\alpha}$, then Theorem 1.2 gives
$|L||A||B|^{1/2}q^{-\alpha/2}$. This is better than (1) and (2) in the range

$q^{\alpha}\max\\{|A|,|L_{x}|\\}<|L||A|<q^{1+\alpha},~{}|A|<q^{\alpha},~{}|L|<q^{\alpha}|B|.$

In the following, we include two examples, one for $|A||L|\ll q^{3\alpha},$
and one for $|A||L|\gg q^{3\alpha}.$

  * •

($|A||L|\ll q^{3\alpha}$) Set $\alpha=\frac{1}{4},$ then let $L_{x}$ be a set
of $q^{\frac{1}{2}}$ different slopes, and pick $q^{\frac{1}{8}}$ different
lines of each slope for a total of $q^{\frac{5}{8}}$ lines. Then pick any
$A,B\subset\mathbb{F}_{q}$ such that $|A|=q^{\frac{1}{12}}$ and
$|B|=q^{\frac{2}{3}}.$

  * •

($|A||L|\gg q^{3\alpha}$) Set $\alpha=\frac{2}{5},$ then let $L_{x}$ be a set
of $q^{\frac{4}{5}}$ different slopes, and pick $q^{\frac{1}{5}}$ different
lines of each slope for a total of $q$ lines. Then pick any
$A,B\subset\mathbb{F}_{q}$ such that $|A|=q^{\frac{4}{15}}$ and
$|B|=q^{\frac{3}{4}}.$

#### Improved ranges of Theorem 1.3:

To see the domains in which the theorem is non-trivial, we recall the
following well-known incidence bounds over arbitrary finite fields, namely,
Vinh’s result in [18]:

$I(P,\Pi)\leq\frac{|P||\Pi|}{q}+2q\sqrt{|P||\Pi|},$ (5)

and the Cauchy-Schwarz incidence bounds:

$I(P,\Pi)\leq q^{1/2}|P|^{1/2}|\Pi|+|P|,~{}q^{1/2}|P||\Pi|^{1/2}+|\Pi|.$ (6)

  1. 1.

If $|P|\gg q^{3\alpha}$, then Theorem 1.3 gives $|P||\Pi|q^{-\alpha}$. This is
better than those in (5) and (6) whenever

$q^{3\alpha}<|P|<q^{1+2\alpha},~{}q^{1+\alpha}<|\Pi|<q^{1+2\alpha},~{}|P||\Pi|<q^{2+2\alpha},~{}|P||\Pi|\ll
q^{4},~{}\alpha\in(0,1/2).$

  2. 2.

If $|P|\ll q^{3\alpha}$, then then Theorem 1.3 gives $q^{2\alpha}|\Pi|$. This
is better than those in (5) and (6) whenever

$q^{4\alpha-1}<|P|<q^{3\alpha},~{}~{}q^{1+\alpha}<|\Pi|<\min\\{|P|^{2}q^{1-4\alpha},|P|q^{2-4\alpha}\\},|P||\Pi|\ll
q^{4}.$

To show that Theorem 1.3 gives new bounds in non-trivial applications, we
include three concrete examples, two for $|P|\ll q^{3\alpha},$ and one for
$|P|\gg q^{3\alpha}.$

  * •

($|P|\ll q^{3\alpha}$ and $|P|<|\Pi|$) Set $\alpha=\frac{1}{5},$ and let $\Pi$
be a set of $q^{\frac{5}{4}}$ planes. Then pick any
$P\subset\mathbb{F}_{q}^{3}$ such that $|P|=q.$

  * •

($|P|\ll q^{3\alpha}$ and $|P|>|\Pi|$) Set $\alpha=\frac{1}{5},$ and let $\Pi$
be a set of $q^{\frac{5}{4}}$ planes. Then pick any
$P\subset\mathbb{F}_{q}^{3}$ such that $|P|=q^{\frac{4}{3}}.$

  * •

($|P|\gg q^{3\alpha}$) Set $\alpha=\frac{1}{3},$ and let $\Pi$ be a set of
$q^{\frac{3}{2}}$ different planes. Then pick any $P\subset\mathbb{F}_{q}^{3}$
such that $|P|=q^{\frac{11}{10}}.$

#### Improved ranges of Theorem 1.4:

To see that Theorem 1.4 also gives new bounds in non-trivial applications, we
include two examples, one for $|\Pi|\ll q^{3\alpha},$ and one for $|\Pi|\gg
q^{3\alpha}.$

  * •

($|\Pi|\ll q^{3\alpha}$) Set $\alpha=\frac{1}{3},$ and let $\Pi$ be a set of
$q^{\frac{8}{9}}$ planes. Then pick any $P\subset\mathbb{F}_{q}^{3}$ such that
$|P|=q^{\frac{1}{2}},$ taking care that no intersection of planes has more
than $k=q^{\frac{1}{8}}$ points of $P$.

  * •

($|\Pi|\gg q^{3\alpha}$) Again, set $\alpha=\frac{1}{3},$ and let $\Pi$ be a
set of $q^{\frac{5}{4}}$ different planes. Then pick any
$P\subset\mathbb{F}_{q}^{3}$ such that $|P|=2q^{\frac{4}{3}}.$ Because
distinct planes can share no more than $q$ points, we simply let $k=q$ in this
case.

######  Remark 1.1.

We note that over prime fields, a better improvement is due to Rudnev in [13],
which states that

$I(P,\Pi)\ll|P|^{1/2}|\Pi|+k|\Pi|,$

where $k$ is the maximum number of collinear points in $P$, $|P|\leq|\Pi|$ and
$|P|=O(p^{2})$ where $p$ is the characteristic of the field.

#### Improved ranges of Theorem 1.6:

Compared to (4), this result is most effective when the two sets have very
different sizes.

  1. 1.

If $|E|\in(q^{2\alpha},q^{3\alpha})$, $\alpha\in(0,1/2)$, and

$|F|\in\left(q,~{}\min\left\\{q^{2-2\alpha},~{}q\cdot\frac{|E|}{q^{2\alpha}}\right\\}\right)\cap(2kq^{\alpha},q^{2}),$

then (4) is weaker than what is offered by Theorem 1.6. More precisely, with
$|F|\in(q,q^{2})$, applying (4) (and switching the roles of $E$ and $F$) gives
us $|\Delta(E,F)|\gg q^{-1}|E|$, which is worse than $q^{-2\alpha}|E|$ when
$\alpha\in(0,1/2)$. If $|E|\in(q^{2\alpha},q^{3\alpha})\cap(0,q)$, then we
have $|\Delta(E,F)|\gg q^{-2}|E||F|$ from (4), which is smaller than
$q^{-2\alpha}|E|$ when $|F|<q^{2-2\alpha}$. If
$|E|\in(q^{2\alpha},q^{3\alpha})\cap(q,q^{2})$, then we have $|\Delta(E,F)|\gg
q^{-1}|F|$, which is also weaker than $q^{-2\alpha}|E|$ when
$|F|<q^{1-2\alpha}|E|$.

  2. 2.

Similarly, if $|E|\in(q^{2\alpha},q^{3\alpha})$ and
$|F|\in\left(2kq^{\alpha},\min\left\\{q^{2-2\alpha},q\right\\}\right)$, then
the bound $q^{-2\alpha}|E|$ by Theorem 1.6 is also better. If $|E|\leq q$ then
(4) gives $|E||F|q^{-2}$ and if $|E|\geq q$ (4) gives $|F|q^{-1}$; both of
these are smaller than $|E|q^{-2\alpha}$ in the range given.

###  1.4 Main ideas

The idea of using the VC-dimension to study incidence questions is not new in
the literature, for instance, Fox, Pach, Sheffer, Suk, and Zahl in [3] proved
the following theorem.

######  Theorem 1.8.

Let $G=(P,Q,E)$ be a bipartite graph with $|P|=m$ and $|Q|=n$ such that the
system $\mathcal{F}_{1}:=\\{N(q)\colon q\in Q\\}$ satisfies
$\pi_{\mathcal{F}_{1}}(z)\leq cz^{d}$ for all $z$. Then, if $G$ is
$K_{k,k}$-free, then

$|E(G)|\leq c_{1}(mn^{1-1/d}+n),$

where $c_{1}=c_{1}(c,d,k)$, and $N(q)$ is the set of neighbors of $q$ in $P$.

We first want to compare between the proof of this theorem and our proofs of
the above incidence bounds. The strategy in the proof of Theorem 1.8 is to do
a number of reductions in which they bounded the number of neighbors of a
single vertex from $Q$ in each step. More precisely, let $\mathcal{F}_{1}$ as
above, and let $\mathcal{F}_{2}=\\{N(u)\colon u\in P\\}$. Given a set
$B\in\mathcal{F}_{2}$ and $k$ points $\\{v_{1},\ldots,v_{k}\\}\subset Q$. We
say that $B$ crosses $\\{v_{1},\ldots,v_{k}\\}$ if
$\\{v_{1},\ldots,v_{k}\\}\not\subset B$ and
$B\cap\\{v_{1},\ldots,v_{k}\\}\neq\emptyset$. It has been proved in [3] that
with such families $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, there exist $k$
points $v_{1},\ldots,v_{k}$ in $Q$ such that at most $2c^{\prime}m/n^{1/d}$
sets from $\mathcal{F}_{2}$ cross $\\{v_{1},\ldots,v_{k}\\}$, where
$c^{\prime}=c^{\prime}(c,d,k)$. For such a $k$-tuples, we observe that the
neighborhood of $q_{1}$ contains at most $c^{\prime\prime}m/n^{1/d}+(k-1)$
points with $c^{\prime\prime}=c^{\prime\prime}(c^{\prime},k)$. This can be
explained from the fact that there are at most $k-1$ points $u_{i}$ such that
$N(u_{i})$ covers $\\{v_{1},\ldots,v_{k}\\}$ (the graph is $K_{k,k}$-free),
and the number of sets crossing $\\{v_{1},\ldots,v_{k}\\}$ is at most
$2c^{\prime}m/n^{1/d}$. Notice that there is a possibility that there are
vertices $u_{1}$ and $u_{2}$ in $P$ such that $N(u_{1})=N(u_{2})$ in
$\mathcal{F}_{2}$, which can be ruled out if we assume that each set in
$\mathcal{F}_{2}$ contains at least $k$ points, then it is clear that
$c^{\prime\prime}\leq kc^{\prime}$. After counting the neighbors of $v_{1}$,
we remove it and repeat the argument for the rest until we have less than $k$
points left.

In the finite fields, the above theorem is not practical at least in two and
three dimensions. For instance, in two dimensions, if we have a set of points
and a set of lines, it is clear that the graph is $K_{2,2}$-free and $d=2$,
thus, it implies nothing but the Cauchy-Schwarz bound. In three dimensions for
points and planes, we know that the graph might contain a very large subgraph,
say $K_{q,q}$. Thus, the factor $c_{1}$ might be very large, which makes the
bound worse. Theorem 1.8 was improved in [6] but the limitations when applying
to these incidence problems remain the same.

As mentioned above, to prove Theorem 1.2, we first prove Theorem 1.4 for
points and planes in $\mathbb{F}_{q}^{3}$ and then use the fact that if the
point set is of Cartesian product structure, then point-line incidences can be
reduced to point-plane incidences. To prove Theorem 1.4, we first define the
graph $G$ with $V(G)=\mathbb{F}_{q}^{3}$, and two vertices are connected by an
edge if the product between them is $1$. It is not hard to check that the VC-
dimension of this graph is at most $3$. Then Lemma 2.1 can be rewritten in the
way that the number of rich planes, i.e. planes with at least a certain number
of points, is bounded. With this information, our theorems follow.

##  2 Preliminaries

In this section, we recall results related to the VC-dimension which can be
found in [3]. Let $U$ be a set and $\mathcal{F}$ and family of subsets of $U$.
We say that a subset $S\subset U$ is shattered by $\mathcal{F}$ if for any
subset $S^{\prime}\subset S$, there is some $A\in\mathcal{F}$ such that $A\cap
S=S^{\prime}$. The VC-dimension of $(U,\mathcal{F})$ is the largest integer
$d$ such that there is a $d$-element subset of $S$ which is shattered by
$\mathcal{F}$. We also recall the definition of the primal shatter function of
$(U,\mathcal{F})$ which is

$\pi_{\mathcal{F}}(z)=\max_{U^{\prime}\subset U,~{}|U^{\prime}|=z}\\#\\{A\cap
U^{\prime}\colon A\in\mathcal{F}\\}.$

Sauer, Shelah, and others (see [15], for example) proved that if $\mathcal{F}$
is a set system with VC-dimension $d$, then

$\pi_{\mathcal{F}}(z)\leq\sum_{i=1}^{d}\binom{z}{i}.$ (7)

To introduce the next concept, we will need to measure the size of the
symmetric difference between two sets, $F_{1},F_{2}\in\mathcal{F}$. We write
$|F_{1}\triangle F_{2}|$, to mean the size of their symmetric difference,
which is given by

$F_{1}\triangle F_{2}=(F_{1}\cup F_{2})\setminus(F_{1}\cap F_{2}).$

A system of sets $\mathcal{F}$ is said to be $(k,\delta)$-separated if for any
$k$ sets $F_{1},\ldots,F_{k}\in\mathcal{F}$, we have

$|(F_{1}\cup F_{2}\cup\cdots\cup F_{k})\setminus(F_{1}\cap F_{2}\cap\cdots\cap
F_{k})|\geq\delta.$

The result we use was called Lemma 2.5 in [3] and is known as the packing
lemma.

######  Lemma 2.1.

Let $\mathcal{F}$ be a $(k,\delta)$-separated system and
$\pi_{\mathcal{F}}(z)\leq cz^{d}$ for all $z$. Then we have $|\mathcal{F}|\leq
c^{\prime}(|U|/\delta)^{d}$ where $c^{\prime}=c^{\prime}(k,d,c)$.

##  3 Proof of Theorem 1.3

Recall that by assumption, $|\Pi|\geq 2q^{1+\alpha}.$ Now set $U=P$ and
$V=\\{a\colon\\{a\cdot x=1\\}\in\Pi\\}$. For each $u\in U$, let $N(u)$ be the
set of $v\in V$ such that $u\cdot v=1$.

Then we can write $I(P,\Pi)$ as

$\displaystyle\sum_{u\in U}|N(u)|=$ $\displaystyle
I(P,\Pi)=\sum_{u\colon|N(u)|\leq
2|V|q^{-\alpha}}|N(u)|+\sum_{u\colon|N(u)|\geq 2q^{-\alpha}|V|}|N(u)|$
$\displaystyle\leq\frac{2|U||V|}{q^{\alpha}}+\sum_{i}\sum_{2^{i}|V|q^{-\alpha}\leq|N(u)|<2^{i+1}|V|q^{-\alpha}}|N(u)|.$

We now show that the number of $u\in U$ such that $|N(u)|\geq
2^{i}|V|q^{-\alpha}$ is at most $(q^{\alpha}2^{-i})^{3}$. Indeed, let
$X_{\alpha}(U)$ be the set of such $u$. Let $\mathcal{G}$ be the set system
(with ground set $V$) defined by $\mathcal{G}:=\\{N(u)\colon u\in
X_{\alpha}(U)\\}$. Since two planes in $\mathbb{F}_{q}^{3}$ either do not
intersect or intersect in a line, and there are at most $q$ points on a line,
this implies

$N(u_{1})\cap N(u_{2})\leq q,~{}\forall~{}u_{1},u_{2}\in U.$

Now, combining this with the fact that $|V|>2q^{1+\alpha},$ we see

$|N(u_{1})\triangle
N(u_{2})|\geq\frac{2^{i}|V|}{q^{\alpha}}-q\geq\left(2^{i}-\frac{1}{2}\right)\frac{|V|}{q^{\alpha}}.$

By a direct computation, it is not hard to see that the VC-dimension of
$\mathcal{G}$ is at most $3$: if there are $4$ planes which contain a point,
then any point in $3$ of them must be in all $4$. Therefore, the inequality
(7) holds with $d=3$. Thus, we now apply Lemma 2.1 with
$\delta=c2^{i}|V|q^{-\alpha},$ for some constant $c$, to conclude that

$|X_{\alpha}(U)|\ll\left(\frac{|V|}{\delta}\right)^{3}\ll\left(q^{\alpha}2^{-i}\right)^{3}.$

So,

$I(P,\Pi)\ll\frac{|U||V|}{q^{\alpha}}+\sum_{i}|V|q^{2\alpha}\frac{1}{2^{2i}}\leq\frac{|U||V|}{q^{\alpha}}+|V|q^{2\alpha}.$

By symmetry, we also have

$I(P,\Pi)\ll\frac{|U||V|}{q^{\alpha}}+|U|q^{2\alpha}.$

##  4 Proof of Theorem 1.4

This proof is very similar to that of Theorem 1.3. Set $U=P$ and
$V=\\{a\colon\\{a\cdot x=1\\}\in\Pi\\}$. For each $v\in V$, let $N(v)$ be the
set of $u\in U$ such that $u\cdot v=1$.

Then we can write $I(P,\Pi)$ as

$\displaystyle\sum_{v\in V}|N(v)|$
$\displaystyle=I(P,\Pi)=\sum_{v\colon|N(v)|\leq
2|U|q^{-\alpha}}|N(v)|+\sum_{v\colon|N(v)|\geq 2q^{-\alpha}|U|}|N(v)|$
$\displaystyle\leq\frac{2|U||V|}{q^{\alpha}}+\sum_{i}\sum_{2^{i}|U|q^{-\alpha}\leq|N(v)|<2^{i+1}|U|q^{-\alpha}}|N(v)|.$

As before, we show that the number of $v\in V$ such that $|N(v)|\geq
2^{i}|U|q^{-\alpha}$ is at most $(q^{\alpha}2^{-i})^{3}$. Indeed, let
$X_{\alpha}(V)$ be the set of such $v$. Let $\mathcal{G}$ be the set system
defined by $\mathcal{G}:=\\{N(v)\colon v\in X_{\alpha}(V)\\}$. Since two
planes in $V$ either do not intersect or intersect in a line, and there are at
most $k$ collinear points in $U$, this implies

$|N(v_{1})\cap N(v_{2})|\leq k,~{}\forall~{}v_{1},v_{2}\in V.$

Thus,

$|N(v_{1})\triangle
N(v_{2})|\geq\frac{2^{i}|U|}{q^{\alpha}}-k\geq\left(2^{i}-\frac{1}{2}\right)\frac{|U|}{q^{\alpha}},$

since $|U|>2kq^{\alpha}$. Again, by a direct computation, it is not hard to
see that the VC-dimension of $\mathcal{G}$ is at most $3$: to shatter a set of
$4$ points they would need to lie in a common plane and in this case any plane
containing $3$ of them must contain all $4$. Therefore, the inequality (7)
holds with $d=3$. Thus, we now apply Lemma 2.1 to conclude that

$|X_{\alpha}(V)|\ll\left(q^{\alpha}2^{-i}\right)^{3}.$

So,

$I(P,\Pi)\ll\frac{|U||V|}{q^{\alpha}}+\sum_{i}|U|q^{2\alpha}\frac{1}{2^{2i}}\leq\frac{|U||V|}{q^{\alpha}}+|U|q^{2\alpha}.$

The theorem follows.

##  5 Proof of Theorem 1.2

Without loss of generality, we assume that the lines are defined by the
equation $y=ax+b$. Since other lines will contribute at most a factor of
$2|P|$ incidences.

By the Cauchy-Schwarz inequality, one has

$I(A\times
B,L)\leq|B|^{1/2}\left(\\#\\{(a,b,x,a^{\prime},b^{\prime},x^{\prime})\in
L\times A\times L\times A\colon
ax+b=a^{\prime}x^{\prime}+b^{\prime}\\}\right)^{1/2}.$

Note that this Cauchy-Schwarz step has also been used in the proof of Stevens-
De Zeeuw point-line incidence result in [17].

The equation $ax+b=a^{\prime}x^{\prime}+b^{\prime}$ can be viewed as an
incidence between the point $(x,a^{\prime},b^{\prime})$ and the plane defined
by $aX-x^{\prime}Y+Z=-b$ in $\mathbb{F}_{q}^{3}$. Let $P$ and $\Pi$ be the
sets of corresponding points and planes in $\mathbb{F}_{q}^{3}$. We note that
any plane in $\Pi$ does not contain any vertical line, so the number of
collinear points $k$ in $P$ can be bounded by $k=\max\\{|A|,|L_{x}|\\}$ when
we do the projection to the $Oxy$ plane. Note that $|P|=|\Pi|=|L||A|$. Thus,
if $|L||A|\geq 2kq^{\alpha}$, then by Theorem 1.4, one has

$\\#\\{(a,b,x,a^{\prime},b^{\prime},x^{\prime})\in L\times A\times L\times
A\colon
ax+b=a^{\prime}x^{\prime}+b^{\prime}\\}\lesssim\frac{|L|^{2}|A|^{2}}{q^{\alpha}}+|L||A|q^{2\alpha}.$

This completes the proof.

##  6 Proof of Theorem 1.5

To prove Theorem 1.5, we need the following lemma. Its proof is standard, but
we include it for completeness.

######  Lemma 6.1.

Let $U$ be a set in $\mathbb{F}_{q}^{3}$ with $|U|\geq 8q^{2}$. Then there
exists a subset $U_{1}$ with $|U_{1}|\gg|U|$ and for any $u\in U_{1}$, the
number of $u^{\prime}\in U$ such that $u\cdot u^{\prime}=1$ is
$\Theta\left(\frac{|U|}{q}\right)$.

###### Proof.

For $u\in U$, let $N(u)$ be the set of $u^{\prime}\in U$ such that $u\cdot
u^{\prime}=1$. Define

$L:=\left\\{u\colon|N(u)|\geq\frac{2|U|}{q}\right\\},~{}R:=\left\\{u\colon|N(u)|\leq\frac{|U|}{2q}\right\\}.$

We identify each point $u\in L$ with the plane defined by $x\cdot u=1$. We
abuse the notation to denote the set of corresponding planes by $L$. Then it
is clear that $I(U,L)\geq 2|U|^{2}/q$. Using the point-plane incidence bound
(5), we have

$\frac{2|U||L|}{q}\leq I(U,L)\leq\frac{|U||L|}{q}+2q\sqrt{|U||L|}.$

This implies $|U||L|\leq 4q^{4}$. Thus, if $|U|\geq 8q^{2}$, then $|L|\leq
q^{2}/2\leq|U|/16$.

Similarly, we have

$\frac{|R||U|}{q}-2q\sqrt{|R||U|}\leq I(R,U)\leq\frac{|R||U|}{2q}.$

This infers $|R||U|\leq 16q^{4}$, so $|R|\leq 2q^{2}\leq|U|/4$.

Set $U_{1}=U\setminus(L\cup R)$, then $|U_{1}|\gg|U|$, and it satisfies the
desired property. ∎

###### Proof of Theorem 1.5.

Let $U_{1}$ be the set defined in Lemma 6.1, i.e. for all $u\in U_{1}$, one
has $|N(u)|=\Theta\left(|U|q^{-1}\right)$. Let $\mathcal{F}:=\\{N(u)\colon
u\in U_{1}\\}$. We note that $|\mathcal{F}|=|U_{1}|\gg|U|$.

It follows from the definition of $\pi_{\mathcal{F}}(|U^{\prime}|)$ and (7)
that

$|\mathcal{F}\cap U^{\prime}|=\\#\\{A\cap U^{\prime}\colon
A\in\mathcal{F}\\}\leq\pi_{\mathcal{F}}(|U^{\prime}|)\ll|U^{\prime}|^{3}$ (8)

For each $S\in\mathcal{F}\cap U^{\prime}$, let $m(S)$ be the number of sets
$A\in\mathcal{F}$ such that $S=A\cap U^{\prime}$. We have
$\sum_{S}m(S)=|\mathcal{F}|$. By Cauchy-Schwarz, we have

$|\mathcal{F}|^{2}\leq|\mathcal{F}\cap U^{\prime}|\cdot\sum_{S}m(S)^{2}.$ (9)

Combining (8), (9), and the lower bound on $|\mathcal{F}|,$ we get

$\sum_{S}m(S)^{2}\gg\frac{|U|^{2}}{|U^{\prime}|^{3}},$

which is what we want to prove.

∎

##  7 Proof of Theorem 1.6

For any $\gamma\in\mathbb{F}_{q}$, let $R_{\gamma}=\\{(e,f):e\in E,f\in
F,||e-f||=\gamma\\}$ and for each $f\in F$ let $R_{\gamma}(f)=\\{e:e\in
E,||e-f||=\gamma\\}$. Additionally, let $T(E,F)$ be the set of triples
$(u,v,x)\in E\times E\times F$ such that $||x-u||=||x-v||\neq 0$. By the
assumption on the number of pairs at distance $0$, we have that

$\displaystyle\frac{|E|^{2}|F|^{2}}{4}$
$\displaystyle\leq\left|\bigcup_{\gamma\not=0}R_{\gamma}\right|^{2}=\left(\sum_{\gamma\not=0}|R_{\gamma}|\right)^{2}$
$\displaystyle\leq|\Delta(E,F)|\sum_{\gamma\not=0}|R_{\gamma}|^{2}=|\Delta(E,F)|\sum_{\gamma\not=0}\left(\sum_{f}|R_{\gamma}(f)|\right)^{2}$
$\displaystyle\leq|\Delta(E,F)|\sum_{\gamma\not=0}\left(|F|\sum_{f}|R_{\gamma}(f)|^{2}\right)=|\Delta(E,F)|\cdot|F|\cdot|T(E,F)|,$

where both inequalities are by Cauchy-Schwarz. Hence, we have

$|\Delta(E,F)|\gg\frac{|E|^{2}|F|}{|T(E,F)|}.$

Fix $u\in E$, we observe that for each $v\in E$, the equation
$||x-u||=||x-v||$ determines a bisector plane in $\mathbb{F}_{q}^{3}$. Let
$\Pi_{u}$ be the set of those planes corresponding to $v\in E$. We now aim to
show that each different choice of $v$ leads to a distinct plane in
$\Pi_{u}.$We note that since $q\equiv 3\mod 4$, any sphere of non-zero radius
does not contain any line, i.e. it intersects a line in at most two points.
This means that the planes in $\Pi_{u}$ are distinct. So

$|T(E,F)|=\sum_{u\in U}I(F,\Pi_{u}).$

Under the assumption that $|F|>2kq^{\alpha}$, and $k$ is the maximal number of
collinear points in $F$ having non-zero distances from any pair of points in
$E\times E$, as in the proof of Theorem 1.4, we have

$I(F,\Pi_{u})\leq\frac{|F||\Pi_{u}|}{q^{\alpha}}+q^{2\alpha}|F|.$

Thus,

$|T(E,F)|\ll\frac{|E|^{2}|F|}{q^{\alpha}}+q^{2\alpha}|E||F|.$

So,

$|\Delta(E,F)|\gg\min\left\\{q^{\alpha},\frac{|E|}{q^{2\alpha}}\right\\}.$

Since $k$ is the maximal number of collinear points in $F$ having non-zero
distances from a pair of points in $E\times E$, we also have
$|\Delta(E,F)|\geq k/2$. Hence, if $|E|\geq q^{3\alpha}$, one has

$|\Delta(E,F)|\gg\max\\{k,q^{\alpha}\\}.$

If $|E|\leq q^{3\alpha}$, then

$|\Delta(E,F)|\gg\max\left\\{k,\frac{|E|}{q^{2\alpha}}\right\\}.$

##  8 Proof of Theorem 1.7

Because of the assumptions that the number of orthogonal pairs in $E\times F$
is at most $|E||F|/2$, by averaging there is some nonzero
$\lambda\in\mathbb{F}_{q}$ satisfying that the number of pairs in $E\times F$
with $u\cdot v=\lambda$ is at least $|E||F|/|D(E,F)|$. Let $M(E,F)$ be the set
of pairs $(u,v)\in E\times F$ such that $u\cdot v=\lambda$. So we have that

$|D(E,F)|\gg\frac{|E||F|}{|M(E,F)|},$

Viewing $E$ as a set of planes and $F$ as a set of points, we apply Theorem
1.4 to obtain

$|M(E,F)|\ll\frac{|E||F|}{q^{\alpha}}+q^{2\alpha}|F|.$

This gives

$|D(E,F)|\gg\min\left\\{q^{\alpha},\frac{|E|}{q^{2\alpha}}\right\\}.$

We now argue that if we have a line $\ell_{0}$ with $k$ points from $F$, say
$\\{u_{1},\ldots,u_{k}\\}\subset\ell_{0}$, then $|D(E,F)|\geq k$. This is more
complicated compared to the case of the distance function.

We first observe that for any $\lambda\not=0$, the intersection of the planes
defined by $u_{i}\cdot x=\lambda$ is a line. To see this, consider the
intersection of the planes $u_{1}\cdot x=\lambda$ and $u_{2}\cdot x=\lambda$
and call this line $\ell_{\lambda}$. Let $w\in\ell_{\lambda}$, then it is
clear that $u_{1},u_{2}$ belongs to the plane defined by $w\cdot x=\lambda$.
Then this plane contains the entire line $\ell_{0}$. Thus, the line
$\ell_{\lambda}$ is what we want to find.

The second observation is that if $v\in E$ and $u_{i}\cdot v=u_{j}\cdot
v=\lambda$, then $u_{i}\cdot v=\lambda$ for all $1\leq i\leq k$. This holds
for any pair $i\not=j$ in $\ell_{0}$.

By definition, the lines $\ell_{\lambda}$ and $\ell_{\beta}$ are parallel for
distinct $\lambda,\beta\neq 0$. Consider the collection of these lines that
have at least one point of $E$ on them. Call these lines
$\ell_{\lambda_{1}},\cdots\ell_{\lambda_{t}}$. Then
$\\{\lambda_{1},\cdots,\lambda_{t}\\}\in D(E,F)$, and so if $t\geq k$ we are
done. If $t<k$, then there must be a $w\in E$ and distinct $u_{i}$ and $u_{j}$
such that $w\cdot u_{i}=w\cdot u_{j}=\lambda$ for some $\lambda\not=0$. By the
observations, we have that the whole line $\ell_{0}$ is contained in the plane
$w\cdot x=\lambda$. Since $E$ is not contained in any single plane, there is
some $w^{\prime}\in E$ which is not contained in this plane, and now
$|D(w^{\prime},\ell_{0})|=k$.

In other words,

$|D(E,F)|\gg\max\left\\{k,~{}\min\left\\{q^{\alpha},\frac{|E|}{q^{2\alpha}}\right\\}\right\\}.$

If $|E|\geq q^{3\alpha}$, one has

$|D(E,F)|\gg\max\\{k,q^{\alpha}\\}.$

If $|E|\leq q^{3\alpha}$, then

$|D(E,F)|\gg\max\left\\{k,\frac{|E|}{q^{2\alpha}}\right\\}.$

##  9 Acknowledgements

A. Iosevich was supported, in part, by te HDR Tripods NSF Grant and NSF DMS
2154232 grant. T. Pham would like to thank to the VIASM for the hospitality
and for the excellent working conditions. M. Tait was partially supported by
National Science Foundation grant DMS-2011553.

## References

  * [1] Jean Bourgain, Nets Katz, and Terence Tao, _A sum-product estimate in finite fields, and applications_ , Geometric & Functional Analysis GAFA 14 (2004), no. 1, 27–57.
  * [2] Javier Cilleruelo, _Combinatorial problems in finite fields and sidon sets_ , Combinatorica 32 (2012), no. 5, 497–511.
  * [3] Jacob Fox, János Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl, _A semi-algebraic version of Zarankiewicz’s problem_ , Journal of the European Mathematical Society 19 (2017), no. 6, 1785–1810.
  * [4] Harald Andrés Helfgott and Misha Rudnev, _An explicit incidence theorem in $\mathbb{{F}}_{p}$_, Mathematika 57 (2011), no. 1, 135–145.
  * [5] Alex Iosevich and Misha Rudnev, _Erdos distance problem in vector spaces over finite fields_ , Transactions of the American Mathematical Society 359 (2007), no. 12, 6127–6142.
  * [6] Oliver Janzer and Cosmin Pohoata, _On the Zarankiewicz problem for graphs with bounded VC-dimension_ , arXiv preprint arXiv:2009.00130 (2020).
  * [7] Timothy Jones, _Explicit incidence bounds over general finite fields_ , Acta Arithmetica 3 (2011), no. 150, 241–262.
  * [8] Timothy GF Jones, _An improved incidence bound for fields of prime order_ , European Journal of Combinatorics 52 (2016), 136–145.
  * [9] Doowon Koh and Hae-Sang Sun, _Distance sets of two subsets of vector spaces over finite fields_ , Proceedings of the American Mathematical Society 143 (2015), no. 4, 1679–1692.
  * [10] Brendan Murphy and Giorgis Petridis, _A point-line incidence identity in finite fields, and applications_ , arXiv preprint arXiv:1601.03981 (2016).
  * [11] Brendan Murphy, Giorgis Petridis, Thang Pham, Misha Rudnev, and Sophie Stevens, _On the pinned distances problem in positive characteristic_ , Journal of the London Mathematical Society 105 (2022), no. 1, 469–499.
  * [12] Giorgis Petridis, Oliver Roche-Newton, Misha Rudnev, and Audie Warren, _An energy bound in the affine group_ , International Mathematics Research Notices 2022 (2022), no. 2, 1154–1172.
  * [13] Misha Rudnev, _On the number of incidences between points and planes in three dimensions_ , Combinatorica 38 (2018), no. 1, 219–254.
  * [14] Misha Rudnev and Ilya D Shkredov, _On the growth rate in ${S}{L}_{2}(\mathbb{{F}}_{p})$, the affine group and sum-product type implications_, Mathematika 68 (2022), no. 3, 738–783.
  * [15] N. Sauer, _On the density of families of sets_ , Journal of Combinatorial Theory, Series A 13 (1972), 145–147.
  * [16] Igor E. Shparlinski, _On the set of distances between two sets over finite fields_ , International Journal of Mathematics and Mathematical Sciences 2006 (2006).
  * [17] Sophie Stevens and Frank De Zeeuw, _An improved point-line incidence bound over arbitrary fields_ , Bulletin of the London Mathematical Society 49 (2017), no. 5, 842–858.
  * [18] Le Anh Vinh, _The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields_ , European Journal of Combinatorics 32 (2011), no. 8, 1177–1181.
  * [19] Josh Zahl, _Finite field Szemeredi-Trotter theorem with unequal number of points and lines_ , MathOverflow, URL:https://mathoverflow.net/q/157976 (version: 2022-02-25).


##  1 Experiments

###  Implementation Details

For data pre-processing, we use MTCNN [zhang2016joint] to detect and align
face and resize all the detected faces to $256\times 256\times 3$ for source
and target samples. Then we randomly sample source domain samples that provide
the contents and the target samples that provide the styles to synthesize the
augmented data using WCT2 [yoo2019photorealistic]. The number of the
synthesized samples is about one tenth of the source. We use ResNet-18
[he2016deep] as the backbone architecture of feature generator and a two nodes
FC layer as the classifier. Domain discriminator contains two FC layers with
512 and 2 nodes, respectively. The Adam optimizer with weight decay of 1e-5
and learning rate of 1e-4 is used for optimization. The hyperparameters
$\lambda_{1}$, $\lambda_{2}$ and $\lambda_{3}$ are set to 1e-3, 1.0 and 10,
respectively. During training, we force every batch to read the same number of
live and spoof images, with 64 from $X^{s}$, 4 from $X^{t}$ and 8 from
$X^{a}$. We implement $\mathcal{L}_{Adv}$ on live images only based on the
observation that the spoof images bring little performance improvements by
applying $\mathcal{L}_{Adv}$, which is consistent with the observations in
[jia2020single]. Please see Supplementary for more details.

###  Experiments on FSDE-FAS

To validate the performance of SASA on few-shot domain expansion problem, we
compare SASA with representative general cross-domain recognition methods and
FAS mathods which are closely related to our setting or approach. CCSA
[motiian2017unified] and FADA [motiian2017few] focus on solving general
supervised domain adaptation (SDA) problems, especially when only few target
training samples are available; SSDG [jia2020single] deals with the domain
generalization face anti-spoofing (DG-FAS) problem and achieves state-of-the-
art performance. All of these methods can fulfill partial but not all the
goals in FSDE-FAS. It is worth mentioning that although part of our task is
similar to AIM-FAS [qin2019learning], which focus on zero-shot and few-shot
face anti-spoofing. However, AIM-FAS uses MAML [finn2017model] strategy for
meta-learning and is orthogonal to our method. And thus the results cannot be
compared fairly, so no comparisons are given here.

Besides, we also compare our results with two baselines. One is the source
only “$baseline$”, and the other is the joint training baseline
“$baseline_{joint}$” by jointly training on the source and few target labeled
samples, both of which are trained with cross-entropy loss. For fairly
comparison, we re-implement CCSA and FADA based on our FAS framework because
their original framework are not designed for FAS. When comparing with SSDG,
we treat the original source domain and the few-shot target domain as two
different source domains for domain generalization, and evaluate the
performance of SSDG on the test sets of both domains. We maintain experiment
settings of SSDG the same as the original paper.

####  Comparison Results

Table : Experimental results on single-target domain benchmark CMOS-ST.
(Notations: C: CelebA-Spoof; M: MSU-MFSD; O: Oulu-NPU; S: SiW)

0.45!  Source Target -2*Protocols -2*Methods APCER(%)↓ BPCER(%)↓ ACER(%)↓
HTER(%)↓ $baseline$ 0.91 1.36 1.14 25.68 $baseline_{joint}$ 0.96$\pm$0.11
1.47$\pm$0.08 1.22$\pm$0.08 15.14$\pm$4.61 CCSA 3.57$\pm$0.71 1.24$\pm$0.47
2.4$\pm$0.31 12.81$\pm$1.99 FADA 1.72$\pm$0.63 1.59$\pm$0.12 1.65$\pm$0.26
14.07$\pm$2.07 SSDG 5.48$\pm$1.47 4.9$\pm$0.71 5.19$\pm$0.6 20.68$\pm$3.15
-6*C $\rightarrow$ M ours 1.02$\pm$0.04 1.29$\pm$0.07 1.16$\pm$0.02
7.21$\pm$2.18 $baseline$ 0.91 1.36 1.14 40.12 $baseline_{joint}$ 0.95$\pm$0.19
1.41$\pm$0.18 1.18$\pm$0.05 25$\pm$2.65 CCSA 3.15$\pm$1.27 1.49$\pm$0.27
2.32$\pm$0.52 20.87$\pm$1.81 FADA 1.83$\pm$0.41 1.71$\pm$0.29 1.77$\pm$0.1
18.61$\pm$4.71 SSDG 6.11$\pm$1.12 5.26$\pm$1.01 5.68$\pm$0.91 30.33$\pm$2.96
-6*C $\rightarrow$ O ours 0.9$\pm$0.07 1.41$\pm$0.07 1.15$\pm$0.03
11.85$\pm$0.89 $baseline$ 0.91 1.36 1.14 24.26 $baseline_{joint}$
0.98$\pm$0.14 1.38$\pm$0.16 1.18$\pm$0.04 20.79$\pm$4.77 CCSA 3.7$\pm$1.27
1.26$\pm$0.49 2.48$\pm$0.43 16.02$\pm$0.8 FADA 1.65$\pm$0.19 1.7$\pm$0.19
1.67$\pm$0.1 18.22$\pm$4.33 SSDG 5.82$\pm$1.23 6.13$\pm$0.5 5.98$\pm$0.63
17.84$\pm$1.28 -6*C $\rightarrow$ S ours 1.11$\pm$0.1 1.29$\pm$0.13
1.2$\pm$0.03 14.46$\pm$1.58

The experimental results on the proposed benchmark CMOS-ST are shown in Table
1. Compared with other SDA and DG-FAS methods, our method can significantly
improve the performance on the target domain while maximally preserve the
performance of the source domain using source data and only a few target
training samples. Compared with $baseline$ and $baseline_{joint}$, CCSA
[motiian2017unified] and FADA [motiian2017few] can make a certain improvement
on the target domain, but sacrifice the performance on the source domain. The
possible explanation is that the alignment methods they used may hurt the
model’s representative capability of the source domain data, so the model
forgot the corresponding discriminative information. The results of SSDG
[jia2020single] collapse in both the source domain and the target domain,
because it is designed to learn shared knowledge from multiple labeled source
domains with relatively balanced amounts of data and lacks a mechanism to deal
with the serious imbalanced cases.

Table : Experimental results on multi-target domain benchmark CMOS-MT.

0.48!  2*Methods Source Target APCER(%)↓ BPCER(%)↓ ACER(%)↓ HTERM(%)↓
HTERO(%)↓ HTERS(%)↓ HTERavg(%)↓ $baseline$ 0.91 1.36 1.14 25.68 40.12 24.26
30.02 $baseline_{joint}$ 1.06±0.12 1.34±0.1 1.2±0.07 22.69±4.96 21.99±1.73
20.87±2.22 21.85±2.41 CCSA 3.72±0.34 1±0.14 2.36±0.18 12.06±1.51 22.75±2.77
13.25±1.23 16.02±1.55 FADA 1.9±0.6 1.77±0.25 1.84±0.23 19.5±3.89 17.69±5.93
16.16±1.67 17.78±1.01 SSDG 7.15±1.98 5.87±1.03 6.51±1.35 19.07±3.49 22.97±4.25
16.34±6.68 19.46±4.25 ours 1.06±0.14 1.3±0.12 1.18±0.02 6.66±1.59 15.77±1.38
14.42±1.31 12.28±0.71

Results on multi-target benchmark CMOS-MT are shown in Table 1. Our method can
consistently obtain considerable performance improvement when the available
few target domain data is a mixture of multiple domains. Our results on SiW
are slightly worse than CCSA, and the improvement on HTER is not as good as
the other two protocols. Because the domain gap between SiW and CelebA-Spoof
is actually larger than others, it is hard to achieve the optimal adaptation
effect on the premise of maintaining the source performance.

###  Ablation Studies

To analyze the influence and interrelationship of each proposed module, we
conduct ablation studies by using a fixed few-shot set in Oulu-NPU as the
example target domain. The experimental results are shown in Table 1 and 1.

Table : Quantitative results of the ablation studies. $X^{s}$ refers to source
domain data, $X^{t}$ refers to target domain data, $X^{a}$ refers to augmented
data. (a) Simply adding the $X^{a}$ into training can improve the performance
on $X^{t}$. (b) $\mathcal{L}_{Lfc}$ can effectively suppress the negative
impact of $X^{a}$ and $\mathcal{L}_{Cont}$ on the source domain. (c)
$\mathcal{L}_{Cont}$ and $\mathcal{L}_{Adv}$ can make full use of the data
from all of the three domains to improve the adaptability of the model on
target individually and perform better when used simultaneously.

0.45!  $X^{s}$ $X^{t}$ $X^{a}$ $\mathcal{L}_{Lfc}$ $\mathcal{L}_{Cont}$
$\mathcal{L}_{Adv}$ ACER(%)↓ HTER(%)↓ 3*(a) 1.14 40.12 1.20 22.63 1.37 17.38
4*(b) 1.37 17.38 1.15 18.21 1.68 14.11 1.17 12.04 4*(c) 1.15 18.21 1.17 12.04
1.16 15.84 1.17 10.32

Table : Comparison with a general data augmentation method.

0.45!  Aug methods APCER(%)↓ BPCER(%)↓ ACER(%)↓ HTER(%)↓ Random Erase
[zhong2020random] 1.49 1.12 1.31 16.48 Style-based (ours) 0.86 1.48 1.17 10.32

Auxiliary Augmented Samples Benefit Target. As shown in Table 1 (a), when only
sufficient source data are used for training, it is easy to achieve good
results on source. However, the adaptability to the target domain is limited.
As long as the training is sufficient, only few target data can actually
improve the performance on $X^{t}$. However, the potential of the few labeled
data are still not fully exploited. By simply adding the augmented data into
joint training without mining the relationship of distributions, the
performance on $X^{t}$ improves to a certain degree with slightly performance
drop on $X^{s}$. Because the augmented data enrich the training set of
$X^{t}$, but may introduce some noise to $X^{s}$. However, we argue that the
proposed augmentation method already alleviates the issue of forgetting of
source compared to existing augmentation methods. To verify our argument, we
conduct the experiments by replacing our style transfer-based data
augmentation method with a traditional one. The results are shown in Table 1,
where an obvious decrease of performance can be observed.

Source Domain Less-forgetting Constraint Ensures the Stability. Though the
proposed augmentation method partially deals with the catastrophic forgetting
on the source domain, the introduction of the augmented samples as well as
domain alignment losses may still bring certain detrimental effects to the
original feature representation of $X^{s}$, which are already discriminative
and representative for the source domain. From Table 1 (b), it can be observed
that the source domain less-forgetting constraint can further greatly
alleviate the issue without losing much adaptability for $X^{t}$. Encouraging
source features to stay in place can make the discriminative features of
target move closer to source, instead of mapping to a new feature space that
might be insufficient for either the source or the target.

Complementary Effects of Instance-level and Distribution-level Alignments.
Contrastive semantic alignment and progressive adversarial learning are two
adopted strategies to improve adaptability on $X^{t}$, which work at instance-
level and distribution-level, respectively. As shown in Table 1 (c), both
methods can boost the target domain performance individually, and the best
results can be achieved when the two methods work together.

In addition to above analyses, we also conducted experiments on evaluating
effectiveness of the progressive adversarial learning strategy. Compared to
the results of non-progressive counterpart (11.94%), around 2% target domain
performance gain is observed in the proposed strategy (10.32%). With the help
of our full method, we have brought more than 100% performance gain on $X^{t}$
at the expense of only 2% fluctuations on $X^{s}$.

###  Visualizations and Analysis

[width=0.47]figure/more_samples.pdf

Figure :  Illustration of sample images of the augmented auxiliary data
generated with WCT2 [yoo2019photorealistic].

Qualitative results. Some sample augmented images generated via style transfer
are shown in Figure 1. Please refer to Supplementary for more example images.
It can be observed that, the synthesized images preserve the source domain
face identity and global arrangement. Moreover, the source domain spoof traces
are also embodied in the hack images. By contrast, the global styles of the
generated images are more consistent with the target domain. Thus, not only
the global domain knowledge (lighting conditions, color/contrast related to
camera parameters) is encoded, the spoof traces specific to the target domain
are also reflected. Therefore, the augmented domain effectively consider the
key knowledge in both the source and target domains, and smoothly bridge the
two domains in the meantime.

[width=0.35]figure/tsne.pdf

Figure :  The t-SNE [maaten2008visualizing] visualizations of the extracted
features. Upper is pretrained by only source data. Lower is learned with our
method, where the features are discriminative w.r.t all the domains.

Distribution visualizations. As shown in Figure 1, we select 128 samples from
$X^{s}$, test set of $X^{t}$ and $X^{a}$ respectively as well as all the few
labeled target samples for feature visualization using t-SNE
[maaten2008visualizing]. As shown in the upper figure, the generated live and
spoof style fusion data locate between source and target domain samples in the
feature space, which can bridge domain gap smoothly. Also, the generated
samples can somewhat simulate the distribution of unseen target test samples.
Without our method, the data of target domain are scattered in the whole
feature space without clear decision boundary, which indicate that the feature
generator provides week discriminant ability on target domain. As shown in the
lower figure, contrastive semantic alignment pulls the cross domain samples of
the same class closer while progressive adversarial learning strengthens
distribution mixing. Thus, most of the target samples can be correctly
classified. More t-SNE visualizations can be referred to Supplementary.