Abstract
The limited dependence between the additive and the multiplicative structure of fields is in the background of a number of explicit constructions of various types of pseudorandom objects. In this direction we study the size of the intersection of (the additive) translates of fibers of the (multiplicative) norm function over finite fields. Besides extending earlier upper bounds, our main focus here is on obtaining lower bounds.
From our results we conclude several consequences in extremal combinatorics. Our motivation is the projective norm graph
NG
(
q
,
t
)
$\text {NG}(q,t)$
NG left parenthesis q comma t right parenthesis
and its small subgraph statistics.
NG
(
q
,
t
)
$\text {NG}(q,t)$
NG left parenthesis q comma t right parenthesis
provides a tight construction for the Turán number of complete bipartite graphs
K
t
,
s
$K_{t,s}$
upper K Subscript t comma s
with
s
>
(
t
−
1
)
!
$s>(t-1)!$
s greater than left parenthesis t minus 1 right parenthesis factorial
; in particular, it does not contain
K
t
,
(
t
−
1
)
!
+
1
$K_{t, (t-1)!+1}$
upper K Subscript t comma left parenthesis t minus 1 right parenthesis factorial plus 1
. Yet, for
t
≥
4
$t\geq 4$
t greater than or equals 4
it is not even known whether
NG
(
q
,
t
)
$\text {NG}(q,t)$
NG left parenthesis q comma t right parenthesis
contains
K
t
,
t
$K_{t,t}$
upper K Subscript t comma t
. The determination of the largest integer
s
(
t
)
$s(t)$
s left parenthesis t right parenthesis
, such that
NG
(
q
,
t
)
$\text {NG}(q,t)$
NG left parenthesis q comma t right parenthesis
contains
K
t
,
s
(
t
)
$K_{t,s(t)}$
upper K Subscript t comma s left parenthesis t right parenthesis
for all large enough prime powers
q
is an important open question with far-reaching consequences, and the best known bounds,
t
−
1
≤
s
(
t
)
≤
(
t
−
1
)
!
$t-1\leq s(t) \leq (t-1)!$
t minus 1 less than or equals s left parenthesis t right parenthesis less than or equals left parenthesis t minus 1 right parenthesis factorial
, are very far apart. In this paper we settle the first open case and establish
s
(
4
)
=
6
$s(4)=6$
s left parenthesis 4 right parenthesis equals 6
. Along the way we also count subgraphs of
NG
(
q
,
t
)
$\text {NG}(q,t)$
NG left parenthesis q comma t right parenthesis
isomorphic to
H
, for any fixed
3
$3$
3
-degenerate graph
H
, and find that projective norm graphs are quasirandom with respect to these parameters. These results go beyond the consequences of the Expander Mixing Lemma and also imply extensions of the work of Alon and Shikhelman on generalized Turán numbers.
Finally, we also give an elementary proof of the
K
4
,
s
$K_{4,s}$
upper K Subscript 4 comma s
-freeness of
NG
(
q
,
t
)
$\text {NG}(q,t)$
NG left parenthesis q comma t right parenthesis
for
s
=
6
(
∑
i
=
0
t
−
4
q
i
)
+
1
$s= 6(\sum _{i=0}^{t-4} q^i) +1$
s equals 6 left parenthesis sigma summation Underscript i equals 0 Overscript t minus 4 Endscripts q Superscript i Baseline right parenthesis plus 1
. This was known before for
t
=
4
$t=4$
t equals 4
only, via a less direct algebro-geometric argument.