# Boolean Expressions in Firewall Analysis

Adam Hamilton, Matthew Roughan, and Giang Nguyen Adam Hamlton, Giang Nguyen
and Matthew Roughan are associated with The Faculty of Sciences Engineering
and technology, University of Adelaide, South Australia, Australia email:
<EMAIL_ADDRESS>received April 19, 2005; revised
August 26, 2015.

###### Abstract

Firewall policies are an important line of defence in cybersecurity,
specifying which packets are allowed to pass through a network and which are
not. These firewall policies are made up of a list of interacting rules. In
practice, firewall can consist of hundreds or thousands of rules. This can be
very difficult for a human to correctly configure [12, 16]. One proposed
solution is to model firewall policies as Boolean expressions and use existing
computer programs such as SAT solvers to verify that the firewall satisfies
certain conditions. This paper takes an in-depth look at the Boolean
expressions that represent firewall policies. We present an algorithm that
translates a list of firewall rules into a Boolean expression in conjunctive
normal form (CNF) or disjunctive normal form (DNF). We also place an upper
bound on the size of the CNF and DNF that is polynomial in the number of rules
in the firewall policy. This shows that past results suggesting a
combinatorial explosion when converting from a Boolean expression in CNF to
one in DNF does note occur in the context of firewall analysis.

###### Index Terms:

Firewalls, Boolean Algebra, Conjunctive Normal Form, Computational Complexity,
Computing Policy, Access Control Lists.

##  I Introduction

Firewalls form one of the first lines of defence in cybersecurity. They help
to protect the network by implementing a security policy, a set of rules that
tells the firewall which packets are allowed to pass through the firewall and
which packets cannot.

The main motivation behind this research is that firewalls are complicated
[16]. When there are a sufficiently large number of interconnected rules, it
becomes difficult for a human to keep track of the policy enforced by the
firewall [16, 12]. Errors in firewall configurations are common in practice,
and can lead to large security holes that compromise entire networks [16]. To
make things easier for a human operator, it is important to be able to reason
about the firewall’s security policy in a computational and mathematical
manner.

A useful tool in the analysis of firewall policies is Boolean algebra. In a
large number of scenarios, the firewall’s security policy can be viewed as a
Boolean expression. Each rule in the security policy consists of an action and
a predicate of a particular type. The firewall works by taking a packet and
comparing the packet’s data against these rules.

Previous work [10, 9, 8, 17] has shown this link between Boolean expressions
and firewall policies, but relatively little has gone into the specific
structure of the Boolean expression. We hope this paper can bridge this gap in
exploring the Boolean structure of firewall policies.

The main contributions of our paper are:

  1. 1.

We provide an efficient encoding of stateless firewall policies as Boolean
expressions with bounds on the size of the resultant Boolean expressions.

  2. 2.

We give an algorithm for translating in polynomial time, firewall policies
from Boolean expressions in CNF to Boolean expressions in DNF and back.

  3. 3.

We prove that the combinatorial explosion when translating between Boolean
expressions in CNF to DNF does not occur in firewall analysis as previously
suggested in [6].

##  II Background and related work

###  II-A Firewall analysis

A firewall is a method of filtering traffic on a computer network. A firewall
sits either at the boundary of, or within a computer network and either allows
packets to pass through the firewall or drops the packet from the network. The
firewall policies that we consider consist of an ordered list of rules; each
is made up of $d$ intervals followed by an action which is either $accept$ or
$reject$. For instance, a firewall rule could say that if the destination port
is between 20 and 40, then allow the packet to pass through the network. A
packet is compared to a rule in the firewall by comparing the number in the
packet’s header to the corresponding interval specified by the rule. If the
numbers in the packet’s header belong to each of the corresponding intervals,
then the rule’s action is applied to the packet.

Here we use the term firewall policy to denote a Boolean expression that
represents the set of packets that are allowed through a firewall. A firewall
rule list is a method of expressing a firewall using an ordered list of rules.

Most firewall rules focus on just five packet header fields: protocol number,
source and destination IP addresses, and source and destination port numbers
[11]. There are other types of firewalls that employ more complex methods of
packet filtering such as stateful policies, or deep packet inspection, but
these are outside the scope of the paper. We do allow for filtering on more
than just the five-tuple described but the important detail is that there can
only be a bounded number of such fields without significantly altering the
TCP/IP protocol.

###  II-B Boolean algebra

When we restrict firewalls to only allow or deny incoming and outgoing
packets, a firewall policy is equivalent to a Boolean expression specifying
which packets will be permitted through the firewall. This idea is useful
because it allows us to express problems in firewall analysis as Boolean
satisfiability (SAT) problems, and to use tools such as SAT solvers to extract
information about the policy [10, 9, 8, 17]. In this section, we define some
common terminology used in Boolean algebra.

A Boolean expression consists of a set of variables $x_{i}$ which can take a
value of 0 or 1. A Boolean expression $EXP$ consists of either a variable, the
negation of an expression $\neg EXP$, the disjunction of two expressions
$EXP_{1}\vee EXP_{2}$, or the conjunction of two expressions $EXP_{1}\wedge
EXP_{2}$. For instance, the following is a Boolean expression: $(x_{1}\vee\neg
x_{2})\vee\neg(x_{3}\wedge\neg x_{1}).$

A normal form is a method of specifying a mathematical object that has a
particular syntactic form. A Boolean expression is in conjunctive normal form
(CNF) if it is the conjunction of one or more clauses: $C_{1}\wedge
C_{2}\wedge\dots\wedge C_{m}$, where each clause $C_{i}$ is of the form
$v_{1}\vee v_{2}\vee\dots\vee v_{n_{i}}$ and each $v_{i}$ is either a variable
or the negation of a variable. Similarly, a Boolean expression is in
disjunctive normal form (DNF) if it is the disjunction of numerous clauses:
$C_{1}\vee C_{2}\vee\dots\vee C_{m}$, where each clause $C_{i}$ is of the
form: $v_{1}\wedge v_{2}\wedge\dots\wedge v_{n_{i}}$ and each $v_{i}$ is
either a variable or the negation of a variable. The restrictive syntax of
normal forms allows one to make statements about the computational complexity
of certain problems. For instance, the problem of determining if a Boolean
expression can evaluate to 1 is called Boolean satisfiability (SAT). If a
Boolean expression is in CNF and every clause consists of at least 3 variables
then solving SAT is an NP-complete [5] problem. However, solving SAT on a
Boolean expression in DNF can be solved in linear time in the size of the DNF
expression [6].

###  II-C Boolean algebra in firewall analysis

Hazelhurst [8, 9] uses Boolean models to make firewall analysis simpler. The
author argues that by expressing firewall policies as Boolean decision
diagrams, managing firewalls becomes easier for a human to understand.
Elmallah and Gouda [7] use Boolean algebra to place lower bounds on the
complexity of certain problems in firewall analysis. The authors define twelve
decision problems in firewall analysis, and show how they can be expressed as
Boolean SAT problems.

Like Boolean expressions, firewall policies can also be expressed in normal
form. In this paper we consider whitelists and blacklists. These are normal
forms of firewalls that are very similar to CNF and DNF of Boolean
expressions. A whitelist is a firewall policy that consists entirely of rules
of the form $<predicate>\rightarrow allow$ followed by a default rule that
denies all other packets. Likewise, a blacklist is a firewall policy whose
rules are of the form $<predicate>\rightarrow deny$ followed by a default rule
that accepts all remaining packets. Whitelists and blacklists have been
studied by Ranathunga et al. [13]. There are advantages to expressing
firewalls as blacklists and whitelists. One notable advantage is that rules
commute when expressed in this way. This in turn has advantages when it comes
to reasoning about firewall configurations. When one wants to add an extra
rule to a firewall in whitelist form, it is not necessary to work out where in
the rule list it needs to placed. The same also applies for firewalls
expressed as blacklists.

In [13] the authors also discuss the advantages of whitelists from a security
perspective. In a safety critical computer system, such as a power plant,
where malicious behaviour can lead to large amounts of damage and loss of life
it is far better to deny a trusted user than allow an untrustworthy user
access. Ranathunga et al. as well as several published best-practice guides to
firewall configuration [12] argue that in a whitelist it is harder for one to
accidentally allow untrustworthy packets past the firewall, because one is
forced to think about the packets that are allowed through. on the other hand,
when one uses deny rules, it can be easier to forget to specify some
undesirable packets.

Firewall policies expressed as a whitelist are similar to Boolean expressions
in DNF, in the sense that a packet is able to pass through the firewall if its
header is contained in the disjunction of the firewalls rules; that is, if the
packet satisfies at least one of the rules. Likewise, an input satisfies a
Boolean expression in DNF if it satisfies at least one of the clauses.
Similarly, a blacklist firewall policy is similar to a Boolean expression in
CNF in that a packet is allowed through the firewall it does not satisfy any
of the reject rules. More formally, a packet is allowed through a firewall
blacklist if it is contained in the conjunction of the negation of each rule.
We use this similarity later in the paper to define a method of translating
firewall policies into Boolean expressions in normal forms.

###  II-D Assumptions in this paper

In their paper [7], Elmallah and Gouda define 12 problems in firewall analysis
and show that they are NP-complete. In doing so, they show that a Boolean
3-SAT problem can be translated into a firewall policy in such a way that
there is a one-to-one correspondence between rules in the firewall and clauses
in the 3-SAT expression. This mapping from 3-SAT to firewalls can be done in
polynomial time, proving the NP-completeness of Elmallah and Gouda’s 12
problems in firewall analysis. However, one of the key ingredients in their
proof is introducing an arbitrary number of packet header fields. We do not
believe this to be a realistic depiction of a computer network. The TCP/IP
protocol suite consists of packets that have a finite number of header fields
[4]. In most works on firewall management there are only 5 packet header
fields that are considered. Even in more complex situations we can assume an
upper bound of 10 to 12 fields.

In order to analyse computational complexity, it is important to specify which
variables are being held constant and which are allowed to increase. In this
paper, we keep the number of packet header fields constant and allow the
number of possible field values such as addresses to increase. This number of
possible addresses is called $B$. It is assumed that $B$ is large but
$\log(B)$ is small or at least manageable. For instance, in IPV6, $B$ would be
$2^{128}$.

Heule et al. [14] reinforce the idea that the number of fields in a packet
header can almost always be assumed to be constant. In [14], the authors
describe a polynomial-time algorithm to answer the firewall implication
problem in [7]. The firewall implication problem is “given two firewalls
$F_{1}$ and $F_{2}$, is it the case that all the packets accepted by $F_{1}$
are also accepted by $F_{2}$?” We extend this work to provide a framework for
designing polynomial time algorithms for all the problems in [7].

Another assumption we make is that every predicate in each rule of the
firewall is made up of queries of the form $X>Y$ or $X=Y$, that is, we treat
each packet header field as a number and we focus only on queries about the
size of the number. Our complexity results would not hold if the firewall was
capable of querying individual bits of a packet header.

###  II-E Firewall decision trees

Firewall decision trees are a useful way of representing a firewall policy. We
use this model of firewall policies as an intermediate step between firewall
policies given as rule lists, and firewall policies given as Boolean
expressions. The reason for using firewall decision trees as an intermediate
model is so we can use results from [1, 2], which place bounds on the size of
the firewall decision tree and use these results to place bounds on the size
of the Boolean expression. A firewall decision tree is a weakly-connected
acyclic digraph used to represent firewall policies. A node in the digraph
with no outgoing edges is called terminal. Every terminal node in the decision
tree is assigned an action, in our case, this action is $accept$ or $deny$.
Every non-terminal node is marked with a name of a field and has outgoing
edges marked with an interval of values. The values on different outgoing
links from the same non-terminal node do not overlap. There is a single node
called the root node such that all edges connected to this node are outgoing
edges. Given any packet $p$, there is exactly one path from the root that
finishes at a terminal node. This terminal node defines the decision made by
the firewall for the packet $p$. For an example of a firewall decision tree,
see Figure 16.

We define the depth of a node $N$ in a tree as the number of edges in the path
from the root node to $N$. Because the decision tree is a tree, this path is
unique. For simplicity, we assume that all nodes of a given depth are marked
with the same field name and that all terminal nodes are located at the same
depth. This convention is not strictly necessary; we could omit certain non-
terminal nodes. This would correspond to a firewall in which some rules do not
depend on certain packet fields. We could also permute some non-terminal nodes
within the tree. This would correspond to a rule where you check the packet
fields in a different order. We ignore these for simplicity.

A decision tree is a simple deterministic finite automaton. To evaluate a
packet against a firewall decision tree, we follow a path from the root down
to the leaf node choosing at each node, the edge whose label corresponds to
the packet’s field value. We can do this by performing a binary search at each
node, looking for the interval that corresponds to our given packet. Since the
intervals in the outgoing edges of each node are disjoint, this path from root
node to terminal node is unique. If we order the outgoing edges of each node,
then we can match a packet against a firewall in $O(\log(n)d)$ time, where $n$
is the number of rules and $d$ is the number of fields in a packet header.

##  III Algorithm for generating firewall decision trees.

In this section, we present an algorithm for translating a firewall rule list
into a firewall decision tree. Based on this algorithm, we can place bounds on
the size of the tree and later place bounds on the efficiency of CNF and DNF
translation.

Let $I$ and $J$ be disjoint intervals on the natural numbers such that the
smallest element of $J$ is larger than the largest element of $I$. We define
the interval $b(I,J)$ as the set of all natural numbers between $I$ and $J$,
$b(0,J)$ the interval of natural numbers smaller than any element of $J$, and
$b(I,\infty)$, the set of natural numbers larger than any element of $I$.

We use $T$ to denote a firewall decision tree. Let $I_{i}$ be the intervals in
the outgoing edges from the origin of $T$, and $T_{i}$ be the subtrees whose
root is the end of $I_{i}$. We abuse notation and use $I_{i}$ to denote both
the directed edge and its label.

We now recursively define the $addrule$ algorithm. It is a recursive algorithm
that takes a rule $r$ and an existing policy, finds which parts of the rule
are already covered by the policy, and then splits $r$ into sub-rules that are
not covered by the policy. A rule is defined as a list
$(r_{1},r_{2},\dots,r_{n},A)$, where each $r_{i}$ denotes an interval over the
natural numbers and $A$ is an action, either accept or deny. We use $r(2,:)$
to denote rule $r$ with the first entry removed, similar to the command “cdr”
in the LISP programming language. A rule can consist of no intervals and a
single action $A$. We begin with the rule $r$ and tree $T$ as inputs.

The Addrule algorithm

addrule(r, T)

if $r$ and $T$ both consist of an action then

$addrule(r,T)=T$

else

let $I_{r}$ be the first interval in the rule $r$.

for each interval $I_{i}$ in the outgoing edges of the root node of $T$ do

if $I_{i}\cap I_{r}$ is nonempty then

split $I_{i}$ into two (possibly empty) edges $I_{i}\cap I_{r}$ and
$I_{i}\setminus I_{r}$. A the end of $I_{i}\setminus I_{r}$ we place the
subtree $T_{i}$, and at the end of $I_{i}\cap I_{r}$, we place the subtree
$addrule(r(2,:),T_{i})$ (the rule $r$ could still refer to packets not in the
domain of the tree).

else

keep $I_{i}$ and its subtree $T_{i}$ in $T$

end if

end for

consider the intervals $b(I_{i},I_{i+1})$, (the intervals between the outgoing
edges of the origin of $T$)

for each interval in [$b(I_{i},I_{i+1})$] do

if $b(I_{i},I_{i+1})\cap I_{r}$ is nonempty then

create an edge from the origin of $T$, with the label $b(I_{i},I_{i+1})\cap
I_{r}$ and the subtree $r(2,:)$ at the end of it.

end if

end for

end if

Figure 1: An algorithm that takes a firewall decision tree and a rule and
returns a new decision tree.

We use vectors and trees interchangeably when we talk about the tree $r(2,:)$.
We represent a vector $v=(v_{1},v_{2},\dots,v_{m})$ as a tree $T_{v}$, by
defining a tree with $m+1$ nodes $n_{0},n_{1},\dots,n_{m}$. We put directed
edges between the nodes $n_{i},n_{i+1}$ for $i=0,\dots n-1$, and the edge
between $n_{i-1},n_{i}$ is marked with $v_{i}$. Essentially, when we express a
vector as a tree, we draw a sequence of connected lines each marked with the
vectors entries.

In order to give the reader a more intuitive understanding of the notation
used in this paper, we have provided a diagram, Figure 2, to demonstrate this
notation.

Figure 2: The intervals that we consider in the first iteration of
$addrule(r,T)$. The intervals $I_{r}$, represents the first interval of rule
$r$, and $I_{1}$, $I_{2}$, and $I_{3}$ are the intervals from the root node of
$T$. We use the red brackets to denote the intervals that we need to consider
in the algorithm. We have made a point of only showing the non-empty
intervals. For instance, since $I_{3}$ is completely disjoint from $I_{r}$, we
do not consider the interval $I_{3}\cap I_{r}$, likewise, we do not need to
consider the empty interval $I_{3}\setminus I_{r}$, but we need to consider
both $I_{1}\cap I_{r}$ and $I_{1}\setminus I_{r}$, since $I_{1}$ and $I_{r}$
overlap.

The diagrams in Figures 3 and 4, show one iteration of the $addrule$
algorithm, showing the new branches created in the firewall decision tree, as
well as their labels and new subtrees.

Figure 3: An abstract example of a firewall policy tree $T$ corresponding to
the rules in Figure 2 to which we will add a rule $r$. The directed edges from
the root node of $T$ are labelled with intervals $I_{1}$, $I_{2}$, and
$I_{3}$, where $I_{1}<I_{2}<I_{3}$. The nodes at the ends of $I_{1}$, $I_{2}$,
and $I_{3}$ are labelled with $T_{1}$, $T_{2}$, and $T_{3}$, where $T_{i}$,
represents both the node at the end of $I_{i}$ and the subtree who’s root node
is $T_{i}$. Figure 4: The first layer of the firewall decision tree shown in
Figures 2-3 after adding $r$ from Figure 2. The three edges from the root node
are replaced by the five intervals from Figure 2. The subtrees at the end of
each edge is $T_{i}$ if the interval contains part of $I_{i}$ and no part of
$I_{r}$ are given by $T_{i}$. The subtrees at the end of an interval that
contains both $I_{r}$ and $I_{i}$ are given by $addrule(r(2,:),T_{i})$, and
the subtrees at the end of an interval that just consists of $I_{r}$ are given
by $r(2,:)$

####  III-1 Concrete example of the addrule algorithm

Here we show an example of the algorithm being used to construct the decision
tree for the following rules in interval notation:

$(1,10)(2,5)(1,10)\rightarrow\text{accept}$
$(3,15)(3,4)(1,10)\rightarrow\text{deny}.$

origin(1, 10)(2, 5)(1, 10) Figure 5: The decision tree created from a single
rule. This takes the list of intervals present in rule
$r=(1,10)(2,5)(1,10)\rightarrow\text{accept}$ and creates a tree with 4 nodes,
and the edges are labelled with the intervals in the rule $r$.

We begin by creating a decision tree from a single rule. This is shown in
Figure 5.

We then take the second rule $(3,15)(3,4)(1,10)\rightarrow\text{deny}$ and
merge it into the decision tree. This is shown in Figure 6.

originacceptdeny(1, 10)(2, 5)(1, 10)(3, 15)(3, 4)(1, 10) Figure 6: The
intermediate decision tree created from two rules connected at the origin.
Observe that the outgoing edges from the origin are marked with overlapping
intervals. This will be fixed in later iterations of the $addrule$ algorithm.
The red edges and labels correspond to packets that rule $r$ refers to but the
tree $T$ does not.

Since the intervals $(1,10)$, $(3,15)$ intersect in $(3,10)$, we split the
intervals up into the three intervals $(1,2)$, $(3,10)$, and $(11,15)$. As
rule 1 is the only rule that corresponds to the interval $(1,2)$, we append
$r(2,:)$ to the end of the edge marked $(1,2)$. This is shown in Figure
LABEL:fig:step3.

originacceptdeny$T_{1}$acceptdeny(1, 2)(2, 5)(1, 10)(3, 10)(3, 4)(1, 10)(2,
5)(1, 10)(11, 15)(3, 4)(1, 10) Figure 7: The first recursion: We add the parts
of $I_{r}$ that do not intersect $I_{1}$ as a separate branch. We now have the
subtree $T_{1}$ which will be resolved in the next iteration of the $addrule$
algorithm. originacceptacceptacceptdenyacceptdeny(1, 2)(2, 5)(1, 10)(3,
10)(2)(1, 10)(3, 4)(1, 10)(1, 10)(5)(1, 10)(11, 15)(3, 4)(1, 10) Figure 8: The
second iteration of the $addrule$ algorithm. All the edges of depth two are
marked with disjoint intervals.

Now that we have completed the decision tree from the origin, we need to merge
rule $r_{2}(2,:)$, into $T_{1}$, the subtree whose root node is the endpoint
of the edge labelled $(3,10)$. So we take the first interval in rule
$r_{2}(2,:)$, (3,4), and the intervals in the outgoing edges of the root node
of $T_{1}$, (2,5). These intervals intersect at $(3,4)$, and rule 2 is not
present at $(2)$, and $(5)$. This is shown in Figure 8.

So now, our final step is to merge the rule $(1,10)\rightarrow deny$, with the
tree, that consists of a single edge $(1,10)\rightarrow accept$. Since the
interval of the tree’s outgoing edge, is a superset of the rule’s interval,
the rule is completely subsumed by the tree and we just have the tree
$(1,10)\rightarrow accept$.

We have now reached the base case. We have a tree that just consists of the
action accept and a rule that just consists of the action deny. As specified
in the algorithm, the accept action takes highest priority and so we have our
decision tree.

originacceptacceptacceptacceptdeny(1, 2)(2, 5)(1, 10)(3, 10)(2)(1, 10)(3,
4)(1, 10)(5)(1, 10)(11, 15)(3, 4)(1, 10) Figure 9: The third and final
iteration of the $addrule$ algorithm. We now have a firewall decision tree
whose edge labels are disjoint.

We now have a decision tree representation of the rules
$(1,10)(2,5)(1,10)\rightarrow\text{accept}$ and
$(3,15)(3,4)(1,10)\rightarrow\text{deny}$. We can translate the decision tree
back into a rule list by taking the paths from the origin to every leaf node.
So the rules $(1,10)(2,5)(1,10)\rightarrow\text{accept}$ and
$(3,15)(3,4)(1,10)\rightarrow\text{deny}$ are equivalent to the list of rules

$\displaystyle(1,2)(2,5)(1,10)$ $\displaystyle\rightarrow\text{accept}$
$\displaystyle(3,10)(2)(1,10)$ $\displaystyle\rightarrow\text{accept}$
$\displaystyle(3,10)(3,4)(1,10)$ $\displaystyle\rightarrow\text{accept}$
$\displaystyle(3,10)(5)(1,10)$ $\displaystyle\rightarrow\text{accept}$
$\displaystyle(11,15)(3,4)(1,10)$ $\displaystyle\rightarrow\text{deny}$

Since the predicates of each rule refers to disjoint sets, the order of the
rules is irrelevant.

Using this algorithm to translate a firewall into a decision tree, the tree
can grow quite quickly. We now introduce the final step of this algorithm
which groups adjacent rules together to create a reduced tree. We say that two
nodes $n_{1}$ and $n_{2}$ of a firewall decision tree are adjacent if and only
if the following three conditions hold:

  1. 1.

$n_{1}$ and $n_{2}$ are sibling nodes i.e., they have the same parent node.

  2. 2.

Let $e_{1}$ and $e_{2}$ denote the edges that connect $n_{1}$ and $n_{2}$ to
their mutual parent node. $e_{1}$ and $e_{2}$ are marked with two intervals
$(a,b)$ and $(c,d)$, where $c=b+1$.

  3. 3.

The sub-trees, with $n_{1}$ and $n_{2}$ as their respective roots are
identical.

Intuitively, we can imagine each rule in the firewall as being a rectangular
hyperprism. In our examples, $d=3$ and we can imagine each rule as a
rectangular prism. When two rules are adjacent we can represent them both
using a single rule. This is the same as putting the two rectangular prisms
together to form a single rectangular prism. The three conditions is a
mathematically rigorous way of stating this.

Two adjacent nodes can be grouped together as follows

  * •

Starting at the terminal nodes, group together all adjacent nodes.

  * •

For every node at depth $i$ for $i\in{d,d-1,\dots,2,1}$, group together all
adjacent nodes.

By starting from the bottom of the tree and proceeding upwards, we ensure that
the sub-trees below two adjacent nodes are actually identical and not just
equivalent. In this algorithm, each node of the tree is visited exactly once,
and thus the algorithm runs in linear time with respect to the number of
nodes.

Consider the decision tree in Figure 9. After grouping adjacent nodes
together, we obtain the tree.

originacceptdeny(1, 10)(2, 5)(1, 10)(11, 15)(3, 4)(1, 10) Figure 10: The
decision trees with adjacent rules grouped together.

###  III-A Whitelist and blacklist translation

It is a simple matter to extract the whitelist and blacklist translations of a
firewall policy from a decision tree. In this subsection we present an
algorithm that does this. A firewall decision tree is called complete when
every packet is mapped to an action. We can make each firewall decision tree
complete by merging it with a deny all or an accept all rule. We continue to
use the example in Figure 10.

We merge this tree with a deny all rule to obtain the following decision tree.
For simplicity, we assume that each packet header field takes on a number from
0 to 15.

origindenyacceptdenydenydeny(11, 15)(1, 15)(1, 15)(1, 10)(2, 5)(1, 10)(11,
15)(11, 15)(3, 4)(11, 15)(3, 4) Figure 11: A complete decision tree given by
taking the decision tree in Figure 10 and adding a deny rule using the addrule
algorithm. Now every possible packet in this space is assigned a unique path
from the tree’s origin to a leaf node.

We can translate the firewall policy into a whitelist by going through the
tree and taking a list of all the paths from the origin to the decision nodes
marked “accept”. Because the paths in the decision tree represent disjoint
sets of packages, it does not matter what order we take these paths. The
whitelist corresponding to Figure 16 is given by:

$(1,10)(2,5)(1,10)\rightarrow\text{accept}$
$(1,15)(1,15)(1,15)\rightarrow\text{deny},$

and the corresponding blacklist is given by

$(1,10)(1)(1,15)\rightarrow\text{deny}$
$(1,10)(2,5)(11,15)\rightarrow\text{deny}$
$(1,10)(6,15)(1,15)\rightarrow\text{deny}$
$(11,15)(1,15)(1,15)\rightarrow\text{deny}$
$(1,15)(1,15)(1,15)\rightarrow\text{accept}.$

In summary, we have shown how to create a Boolean decision tree from a rule
list using the addrule algorithm. We’ve seen how it takes a rule and
recursively finds the components of the rule disjoint form the tree and adds
these components to the tree.

##  IV Extracting Boolean expressions from firewall decision trees

In this section, we provide an algorithm that extracts Boolean expressions
from firewall decision trees. We then show that based on this algorithm, the
size of the Boolean expressions are within a polynomial factor of each other.

Every firewall rule list consists of rules of the form
$<predicate>\rightarrow<action>$, We will first show how each predicate can be
expressed as a Boolean formula and how, these formulas can be combined
together to give a Boolean expression that describes the firewall policy.
Consider the following rule:

$x_{1}\in[0,108]\wedge x_{2}\in[21,655]\wedge x_{3}\in[7,616]\rightarrow
accept.$

Each rule consists of $n$ statements of the form $x_{i}\in[a,b]$, where $a$
and $b$ are (not necessarily distinct) integers. We show how to derive an
expression for $x_{i}\in[a,b]$ by using an interval tree. We then use the
interval tree to augment the firewall decision tree to obtain a Boolean
decision diagram. Using some simple combinatorial arguments, we show that the
size of the firewall policy, represented as a Boolean expression in CNF/DNF
can be bounded above by the size of the firewall policy expressed as a
blacklist/whitelist multiplied by a constant factor.

The key technique used is that numbers can be represented as bit vectors. For
example, an address segment is a number between 0 and 255. At a lower level,
the address segment is a vector of 8 bits. The 8-bit number $x$ can be
represented by the bit vector $(x_{7},...,x_{0})$, where each $x_{i}$ is a
Boolean variable. Using $f$ to represent 0 and using $t$ to represent 1, the
condition that the bit vector $x$ is equal to 5, is
$x_{7},...,x_{0}=f,f,f,f,f,t,f,t$. This yields the Boolean expression $\neg
x_{7}\wedge\neg x_{6}\wedge\neg x_{5}\wedge\neg x_{4}\wedge\neg x_{3}\wedge
x_{2}\wedge\neg x_{1}\wedge x_{0}$.

###  IV-A Segment trees

In the previous subsection, we showed how to represent numbers as bit vectors
and how we can create a Boolean expression that checks equality. In this
subsection, we show how to efficiently represent intervals using segment
trees. The simplest method to represent intervals is to represent all the
numbers in the interval as bit vectors and take their disjunction. For an
interval $[a,b]$, this results in a Boolean expression that has $b-a$ clauses.

We can reduce this to $O(4\log(B))$ clauses, where $B$ is the size of the
address space, by expressing our interval using a segment tree [3]. A segment
tree is a data structure designed to represent interval data. A segment for a
set of intervals taking values in the range $(0,B)$ uses $O(B\log B)$ storage
and can be built in $O(B\log B)$ time [3]. There are certain optimisations
that can make the tree smaller by placing restrictions of the types of packets
that can be encountered. For the sake of simplicity, we do not consider these
optimisations.

In Figure 12 we show a depth-4 segment tree. This tree can represent intervals
between 0 and 15.

Figure 12: An interval tree of depth 4. The edge labels represent the Boolean
variables used to express the numbers on the leaf nodes.

This is a binary tree. We assign a Boolean variable to each layer of the tree.
The origin is assigned $x_{0}$, the second layer is assigned $x_{1}$, and so
on. Every node in the terminal layer, can be written in binary notation, such
that the binary notation of the number at the terminal node also represents
the instructions for how to reach that number in the tree. For instance the
number 4 can be written in binary as 0011 or be given as the set of
directions: “go left, left, right, and right down the tree”. We can now
identify all the nodes in the segment tree by a binary string and call this
the sequence of a node.

Now that we have a decision tree, we give an example of expressing the
interval $[3,13]$ using the tree and extracting a Boolean expression that is
only satisfied by a bit vector with value between 3 and 13 inclusive. We do
this by first identifying all the paths in the tree that terminate at one of
these numbers. Then we alter the decision tree according to the following
rules:

Figure 13: The interval tree from Figure 12, with the paths from the root to
nodes whose labels are between 3 and 13 shown in red.

  1. 1.

If a node $n$ and it’s neighbour $n^{\prime}$ are marked and both have no
marked descendants, then remove the mark from both $n$ and $n^{\prime}$ and
mark the parent node of $n$ and $n^{\prime}$.

  2. 2.

Terminate this process when it is impossible to remove any more marked nodes.

After applying these rules to the decision tree, we call the result a reduced
decision tree. We use this terminology because the Boolean expression
associated with the interval tree is reduced. We apply these rules to Figure
13, we obtain the reduced, interval tree.

Figure 14: The interval tree from figure 13 with the redundant edges removed.

Now that we have the reduced interval tree, we can obtain a Boolean expression
for the interval $[3,13]$, by taking the disjunction of every marked path from
the root node. From our reduced interval tree in Figure 14, we obtain the
Boolean expression

$\neg x_{0}\neg x_{1}x_{2}x_{3}\vee\neg x_{0}x_{1}\vee x_{0}\neg x_{1}\vee
x_{0}x_{1}\neg x_{2}.$

###  IV-B Boolean decision trees of firewall policies

We now show how to combine the segment tree data structures and the firewall
decision trees to create a Boolean decision tree representation of a firewall
policy. We start by taking the firewall decision tree from Section II-E and
represent all the outgoing edges in the firewall decision tree using a segment
tree. Here we show an example involving the complete decision tree from Figure
16. For simplicity, we denote the subtrees rooted at the end of the $(1,10)$
edge as $T_{1}$ and $T_{2}$, respectively.

The main idea is to take the intervals in each edge of the decision tree and
to replace this edge with an interval tree.

originT1T2(11, 15)(1, 10) Figure 15: The decision tree whose edges are marked
with intervals

We can express the two intervals $(1,10)$ and $(11,16)$ using the segment tree
in Figure 16.

originT1T1T2$x_{1}$$\neg x_{1}$$x_{2}$$\neg x_{2}$ Figure 16: The same
decision tree whose vertices are marked with Boolean variables.

We can proceed down the tree and express the intervals as binary decision
trees until the entire firewall policy is translated into a BDD.

###  IV-C CNF and DNF reformat

######  Theorem 1.

Given a firewall decision tree expressed as a Boolean decision diagram, the
firewall policy expressed in CNF and in DNF can be extracted from the diagram
in time that is polynomial in the number of firewall rules $n$.

###### Proof.

The Boolean expression in DNF can be found by going through the Boolean
decision diagram and counting the number of paths from the root node to the
terminal node marked “1”.

The number of variables in each clause is at most $\log(B)$, where $B$ is the
largest possible interval that we can have for $[a,b]$. The number of clauses
is at most $2\log(B)$. There are at most $d$ intervals in the rule.

Here we provide a loose upper bound on the size of the number of paths from
the root node to the terminal node marked “1”. In the firewall decision tree
for a policy $P$, there are at most $(2n-1)^{d}$ terminal nodes. This means
that there are at most $(2n-1)^{d}$ rules in the firewall expressed as a
whitelist. We consider the interval tree for each interval used to mark the
edges in the firewall decision tree. There are at most $(2\log(B))$, clauses
in the Boolean expression that describe each interval. We can build a DNF
representation of the firewall policy by going along every path from the root
node to the decision node marked “1” and for every edge crossed, adding the
path from the interval tree to our clause and then taking the disjunction of
all of the clauses. The number of clauses in a Boolean expression is at most
$(2\log(B))^{d}(2n-1)^{d}$, which remains polynomial in the number of rules
$n$. ∎

We can obtain a CNF representation of the firewall policy $P$ by counting all
the paths from the root node to the terminal node labelled with ”0”. This is
the negation of $P$ expressed as a Boolean expression in DNF, denoted by $\neg
P$. We then take the negation of $\neg P$ to obtain $\neg\neg P$, an
expression equivalent to $P$. Since $\neg P$ is in DNF, we can obtain an
expression for $P$ in CNF through a straightforward application of DeMorgan’s
law

$\neg\bigwedge_{i=1}^{C}\big{(}\bigvee_{j=1}^{K_{i}}t_{i}^{j}\big{)}=\bigvee_{i=1}^{C}\big{(}\bigwedge_{j=1}^{K_{i}}\neg
t_{i}^{j}\big{)}.$

Since the number of nodes in the firewall decision tree is upper-bounded by
$(2n-1)^{d}$, the number of rules in a firewall expressed as a blacklist is
also $(2n-1)^{d}$ and therefor the number of clauses in the CNF of the Boolean
expression is at most $(2\log(B))^{d}(2n-1)^{d}$.

######  Corollary IV.1.

Let $P$ be a family of firewall policies, let $P_{rule}$ be the size of these
policies expressed as a rule list, and let $P_{FO}$ be the size of the
firewall policy expressed in first order logic. There exists some family of
policies $P$ such that $P_{rule}\in O(2^{P_{FO}})$.

###### Proof.

In section IV-C saw that the DNF and CNF of firewall policies are within a
degree $d$ polynomial factor of one another. If we were to consider packet
spaces with $d+1$ fields then, we would obtain a family of Boolean
expressions, whose CNF and DNF forms are within a degree $d+1$ polynomial of
each other. It is well known that Boolean formulas in DNF can be exponentially
larger than the expression in CNF [15]. Let $P$ be a sequence of Boolean
expressions that have this property.

Since the Boolean expression in DNF is within a polynomial factor of the
firewall policy as a rule list, we need an exponential number of rules in the
rule list to create these policies. So the size of these policies expressed as
rule-lists must be exponentially larger than the formula expressed in first-
order logic in CNF. ∎

##  V Conclusion

In this paper we have made and have justified the following points. Under the
assumption of finitely many packet header fields, Firewall policies can be
expressed as Boolean expressions such that the expression in CNF and the
expression in DNF have sizes that are both $d$ dimensional polynomials of the
original number of rules. Firewall policies in CNF can be translated to their
DNF counterparts in polynomial time, an exponential improvement over naive
expansion.

In the future we hope to extend these

## Acknowledgment

The authors would like to thank Boeing Defence Australia, and the ARC Centre
of Excellence for Mathematical and Statistical Frontiers.

## References

  * [1] Acharya, H. B., Joshi, A., and Gouda, M. G. Firewall modules and modular firewalls.  In The 18th IEEE International Conference on Network Protocols (2010), pp. 174–182.
  * [2] Acharya, H. B., Kumar, S., Wadhwa, M., and Shah, A. Rules in play: On the complexity of routing tables and firewalls.  In 2016 IEEE 24th International Conference on Network Protocols (ICNP) (2016), pp. 1–10.
  * [3] Berg, M. d., Kreveld, M. v., Overmars, M., and Schwarzkopf, O. Computational geometry.  In Computational geometry. Springer, 1997, pp. 212–217.
  * [4] Collins, L. Chapter 10 - securing the infrastructure.  In Cyber Security and IT Infrastructure Protection, J. R. Vacca, Ed. Syngress, Boston, 2014, pp. 247–267.
  * [5] Cook, S. A. The complexity of theorem-proving procedures.  In Proceedings of the Third Annual ACM Symposium on Theory of Computing (New York, NY, USA, 1971), STOC ’71, Association for Computing Machinery, p. 151–158.
  * [6] Davey, B. Introduction to lattices and order.  Cambridge University Press, Cambridge [England], 1990.
  * [7] Elmallah, E. S., and Gouda, M. G. Hardness of firewall analysis.  IEEE Transactions on Dependable and Secure Computing 14, 3 (2017), 339–349.
  * [8] Hazelhurst, S. Algorithms for analysing firewall and router access lists.  ArXiv cs.NI/0008006 (2000).
  * [9] Hazelhurst, S., Attar, A., and Sinnappan, R. Algorithms for improving the dependability of firewall and filter rule lists.  In Proceeding International Conference on Dependable Systems and Networks. DSN 2000 (Los Alamitos CA, 2000), IEEE, pp. 576–585.
  * [10] Heule, M. J. H., Reaz, R., Acharya, H. B., and Gouda, M. Analysis of computing policies using SAT solvers.
  * [11] Liu, A. X., and Liu, A. X. Firewall design and analysis, vol. 4 of Computer and network security.  World Scientific Publishing Co. Pte. Ltd, Singapore, 2010.
  * [12] Ranathunga, D. Auto-configuration of Critical Network Infrastructure.  PhD thesis, University of Adelaide, 2017.
  * [13] Ranathunga, D., Roughan, M., Kernick, P., and Falkner, N. The mathematical foundations for mapping policies to network devices.  In SECRYPT (2016), pp. 197–206.
  * [14] Reaz, R., Ali, M., Gouda, M. G., Heule, M. J. H., and Elmallah, E. S. The implication problem of computing policies.  In Stabilization, Safety, and Security of Distributed Systems (Cham, 2015), A. Pelc and A. A. Schwarzmann, Eds., Springer International Publishing, pp. 109–123.
  * [15] Velev, M. Efficient translation of boolean formulas to cnf in formal verification of microprocessors.  In ASP-DAC 2004: Asia and South Pacific Design Automation Conference 2004 (IEEE Cat. No.04EX753) (2004), pp. 310–315.
  * [16] Wool, A. A quantitative study of firewall configuration errors.  Computer 37, 6 (2004), 62–67.
  * [17] Zhang, S., Mahmoud, A., Malik, S., and Narain, S. Verification and synthesis of firewalls using sat and qbf.  In 2012 20th IEEE International Conference on Network Protocols (ICNP) (2012), pp. 1–6.

|  Adam Hamilton obtained his bachelor’s in mathematical science and his
honours degree in mathematical and computer science from the University of
Adelaide. He is currently pursuing a doctorate in mathematical and computer
science at the University of Adelaide under the supervision of Professor
Matthew Roughan and Dr Giang Nguyen. His research interests include the theory
of computation, computational complexity, randomised algorithms, and time
difference of arrival geolocation.
---|---
|  Prof Matthew Roughan obtained his PhD in Applied Mathematics from the
University of Adelaide in 1994. He has since worked in various industry
related positions with Australian Defence, with Ericsson at the the University
of Melbourne and at AT&T Shannon Research Labs in the United States. For the
last decade or so he has worked in the School of Mathematical Sciences at the
University of Adelaide, in South Australia. His research interests range from
stochastic modelling to measurement and management of networks like the
Internet. In 2018 he was elected to be a Fellow of the ACM, and in 2019 a
Fellow of the IEEE for his work on Internet measurement, and he was a Chief
Investigator in the ARC Centre of Excellence for Mathematical and Statistical
Frontiers.
---|---
|  Dr Giang Nguyen Giang Nguyen is a Senior Lecturer in Applied Mathematics at
the University of Adelaide. Her research interests include stochastic
differential equations, regime-switching diffusions, matrix-analytic methods,
branching processes, and the Hamiltonian cycle problem. She received a PhD
from the University of South Australia in 2009, and completed her postdoctoral
studies at the Universite libre de Bruxelles (2009-2012) and at the University
of Adelaide (2012-2013). She was the inaugural Treasurer of the Australian
Mathematical Society Women in Mathematics Special Interest Group (WIMSIG)
(2013-2018), and the Director of Gender Equity, Diversity and Inclusion of the
Faculty of Engineering, Computer and Mathematical Sciences, the University of
Adelaide (2019-2020). She was a 2019 South Australia Tall Poppy Winner.
---|---


# Radial projection theorems in finite spaces

Ben Lund and Thang Pham and Vu Thi Huong Thu  Discrete Mathematics Group,
Institute for Basic Science (IBS<EMAIL_ADDRESS>Hanoi University of
Science, Vietnam National University<EMAIL_ADDRESS>Hanoi
University of Science, Vietnam National University
<EMAIL_ADDRESS>
###### Abstract.

Motivated by recent results on radial projections and applications to the
celebrated Falconer distance problem, we study radial projections in the
setting of finite fields. More precisely, we extend results due to Mattila and
Orponen (2016), Orponen (2018), and Liu (2020) to finite spaces. In some
cases, our results are stronger than the corresponding results in the
continuous setting. In particular, we solve the finite field analog of a
conjecture due to Liu and Orponen on the exceptional set of radial projections
of a set of dimension between $d-2$ and $d-1$.

##  1\. Introduction

For any point $y\in\mathbb{R}^{d}$, the radial projection
$\pi^{y}:\mathbb{R}^{d}\setminus\\{y\\}\rightarrow S^{d-1}$ is

$\pi^{y}(x)=\frac{x-y}{|x-y|}.$

For $E\subset\mathbb{R}^{d}$, the radial projection of $E$ from $y$ is

$\pi^{y}(E)=\\{\pi^{y}(x):x\in E\setminus\\{y\\}\\}.$

There are many results and open problems related to the general question: What
can be said about the radial projections
$\\{\pi^{y}(E):y\in\mathbb{R}^{d}\\}$, given a bound on the Hausdorff
dimension $\dim_{H}(E)$ of $E$?

Here we consider finite analogs to various results on this general question.
Over a general field $\mathbb{F}$, for a given point $y\in\mathbb{F}^{d}$, the
radial projection $\pi^{y}$ from $y$ maps a point $x\neq y$ to the line that
contains $x$ and $y$. Usually we work over a finite field $\mathbb{F}_{q}$,
and in this setting the standard analog to $\dim_{H}(E)$ is $\log_{q}(|E|)$.

One reason to be interested in finite analogs is that working in the finite
field model can help to understand the behavior of the corresponding problems
in the continuous setting. A second reason that we are interested in radial
projections of point sets is because of a connection to the Falconer distance
problem. Recent work on the Falconer distance problem [6, 7] relies on a
radial projection theorem due to Orponen [21]. We hope that a better
understanding of radial projections of finite point sets may also lead to
progress on finite versions of the Falconer distance problem - see the last
paragraph for a more detailed discussion.

Mattila and Orponen [16] proved that for any Borel set
$E\subset\mathbb{R}^{d}$, if $\dim_{H}(E)>d-1$, then

(1) $\dim_{H}\\{y\in\mathbb{R}^{d}\colon\mathcal{H}^{d-1}(\pi^{y}(E))=0\\}\leq
2(d-1)-\dim_{H}(E),$

where $\mathcal{H}^{d}$ denotes the $d$-dimensional Hausdorff measure. Orponen
showed [21] that this is sharp in the sense that for any $\alpha\in(d-1,d]$,
there exists a Borel set $E\subset\mathbb{R}^{d}$ of Hausdorff dimension
$\alpha$ such that
$\dim_{H}\\{y:\mathcal{H}^{d-1}(\pi^{y}(E))=0\\}=2(d-1)-\alpha$.

Our first result is an analogous bound for sets in finite space.

######  Theorem 1.1.

Let $E\subset\mathbb{F}_{q}^{d}$ and let $M$ be a positive integer, with
$|E|\geq 6q^{d-1}$ and $M\leq 4^{-1}q^{d-1}$. Then,

(2) $\\#\\{y\in\mathbb{F}_{q}^{d}\colon|\pi^{y}(E)|\leq
M\\}<12q^{d-1}M|E|^{-1}.$

This is stronger than the most natural finite analog to (1) in the case that
$M$ is much smaller than $q^{d-1}$, and suggests the following strengthening
of (1).

######  Conjecture 1.2.

Let $E\subset\mathbb{R}^{d}$ be a Borel set with $\dim_{H}(E)>d-1$, and let
$s\leq d-1$ be a real number. Then,

$\dim_{H}\\{y\in\mathbb{R}^{d}:\dim_{H}\pi^{y}(E)<s\\}\leq d-1+s-\dim_{H}(E).$

Liu [13] proved that for any Borel set $E\subset\mathbb{R}^{d}$ with
$\dim_{H}(E)\leq d-1$,

(3)
$\dim_{H}\\{y\in\mathbb{R}^{d}\colon\dim_{H}\pi^{y}(E)<\dim_{H}(E)\\}\leq\min(2(d-1)-\dim_{H}(E),\dim_{H}(E)+1).$

Liu and Orponen [13] further suggested the following, stronger conjecture.

######  Conjecture 1.3.

Let $E\subset\mathbb{R}^{d}$ be a Borel set with $\dim_{H}(E)\in(k-1,k]$ for
$k\in\\{0,1,\ldots,d-1\\}$. Then

$\dim_{H}\left\\{y\in\mathbb{R}^{d}\colon\dim_{H}\pi^{y}(E)<\dim_{H}(E)\right\\}\leq
k.$

We prove the natural finite field analog to Conjecture 1.3 for $|E|\geq
q^{d-2}$.

######  Theorem 1.4.

Let $E\subset\mathbb{F}_{q}^{d}$ with $|E|\leq 100^{-1}q^{d-1}$. Then,

(4) $\\#\\{y\in\mathbb{F}_{q}^{d}:|\pi^{y}(E)|\leq 10^{-1}|E|\\}<8q^{d-1}.$

For $|E|<q^{d-2}$, we prove the following bound, which is slightly stronger
than the natural analog to (3) over the corresponding range.

######  Theorem 1.5.

Let $E\subset\mathbb{F}_{q}^{d}$ and let $1<C<|E|$. Then,

(5) $\\#\\{y\in\mathbb{F}_{q}^{d}:|\pi^{y}(E)|<C^{-1}|E|\\}<(C-1)^{-1}q|E|.$

We do not believe that Theorem 1.5 is sharp, and offer the following
conjecture, which is a natural finite analog to Conjecture 1.3.

######  Conjecture 1.6.

Let $E\subset\mathbb{F}_{q}^{d}$ with $q^{k-1}<|E|\leq q^{k}$ for
$k\in\\{1,\ldots,d-1\\}$. Then,

$\\#\\{y\in\mathbb{F}_{q}^{d}:|\pi^{y}(E)|<10^{-1}|E|\\}\leq 10q^{k}.$

If true, then Conjectures 1.3 and 1.6 would be best possible, up to constant
factors. Indeed, if $E$ is contained in a translate of a $k$-dimensional
subspace $F$, then $\dim_{H}\pi^{y}(E)\leq k-1$ for every $y\in F$. However,
in some cases it is possible to obtain stronger conclusions by assuming that
$E$ is not nearly contained in a translate of a low-dimensional subspace. For
example, Orponen showed that, if $E\subset\mathbb{R}^{2}$ is a Borel set such
that $\dim_{H}(E\setminus\ell)=\dim_{H}(E)$ for each line $\ell$, then

(6)
$\dim_{H}\left\\{y\in\mathbb{R}^{2}\colon\dim_{H}\pi^{y}(E)<\frac{\dim_{H}(E)}{2}\right\\}=0.$

As a consequence of this result, when $\dim_{H}(E)>0$ and
$\dim_{H}(E\setminus\ell)=\dim_{H}(E)$ for each line $\ell$, there exists
$y\in E$ such that $\dim_{H}\pi^{y}(E)>\frac{\dim_{H}(E)}{2}$. Several
improvements have been obtained in [14, 26, 27]. The most recent, due to
Shmerkin and Wang [27], states that for a fixed $k\in\\{1,\ldots,d-1\\}$,
$d\geq 2$, and a Borel set $E\subset\mathbb{R}^{d}$ with
$\dim_{H}(E)=s\in(k-1/k-\eta(d),k]$, where $\eta(d)$ is a small positive
constant satisfying $\eta(1)=0$, then

(7) $\sup_{y\in E}\dim_{H}\pi^{y}(E)\geq
k-1+\phi(s-k+1),~{}~{}\phi(u)=\frac{u}{2}+\frac{u^{2}}{2(2+\sqrt{u^{2}+4})},$

under the condition that $E$ is not contained in any $k$-plane. Hence, with
$d=2$ and $k=1$, one has there exists $y\in E$ such that

(8) $\dim_{H}\pi^{y}(E)\geq\phi(s)>s/2.$

The following finite analog to (6) has a very simple proof, using only the
fact that there is a unique line through any pair of points.

######  Theorem 1.7.

Let $\mathbb{F}$ be an arbitrary field, and let $E\subset\mathbb{F}^{d}$ be a
finite set of points such that no line contains more than $(3/4)|E|$ points of
$E$. Then,

(9) $\\#\\{y\in\mathbb{F}^{d}:|\pi^{y}(E)|<2^{-1}|E|^{1/2}\\}\leq 1.$

In a general setting, we have the next theorem.

######  Theorem 1.8.

Let $\mathbb{F}$ be an arbitrary field and $E$ be a set in $\mathbb{F}^{d}$
such that no line contains more than $|E|/2$ points of $E$. For $M<|E|/4$, we
have

$\\#\\{y\in\mathbb{F}^{d}:|\pi^{y}(E)|<M\\}<4M^{2}.$

This theorem is essentially sharp up to constant factors. For example, suppose
that $\mathbb{F}_{q}$ has a subfield of order $p$, and that
$E\subset\mathbb{F}_{q}^{2}$ is the set of points in a subplane isomorphic to
$\mathbb{F}_{p}^{2}$. Then, $|\pi^{y}(E)|=p+1>|E|^{1/2}$ for every point $y\in
E$.

We can reasonably hope to improve Theorem 1.8 under the additional assumption
that $\mathbb{F}$ does not have a subfield of suitable size. We obtain some
such improvements using incidence bounds, in particular the Szemerédi-Trotter
theorem in the real plane [29] and an analog proved by Stevens and de Zeeuw
for planes over fields of finite characteristic [28].

######  Theorem 1.9.

There exist constants $0<c_{1},c_{2}<1$ such that the following holds. For any
finite $E\subset\mathbb{R}^{2}$ such that $|\ell\cap E|<c_{1}|E|$ for each
line $\ell$ and $M\leq c_{2}|E|$, we have

$\\#\\{y\in\mathbb{R}^{2}:|\pi^{y}(E)|<M\\}<O(M^{2}|E|^{-1}).$

One corollary to Theorem 1.9 (in the spirit of (8)) is that, for any finite
set $E\subset\mathbb{R}^{2}$ with no more than $c_{1}|E|$ points contained in
any line, there is a point $y\in E$ such that $|\pi^{y}(E)|=O(|E|)$.

######  Theorem 1.10.

There exists a constant $0<c<1$ such that the following holds. Let $p$ be
prime. For any set $E\subset\mathbb{F}_{p}^{2}$ with $|E|\ll p^{8/5}$ and
$|\ell\cap E|<c|E|$ for each line $\ell$ and $M\leq c^{11/7}|E|^{4/7}$, we
have

$\\#\\{y\in\mathbb{F}_{p}^{2}:|\pi^{y}(E)|<M\\}<O(M^{11/4}|E|^{-1}).$

We conjecture that the conclusion of Theorem 1.9 holds for sets
$E\subset\mathbb{F}_{p}^{2}$ with $|E|\ll p$ and no more than $c|E|$ points in
any line.

The Falconer distance problem: Another motivation of this work that we want to
emphasize here is a connection between this topic and the Falconer distance
problem, which is one of central problems in Geometric Measure Theory. Given a
compact set $E$ in $\mathbb{R}^{d}$, the Falconer distance conjecture states
that if the Hausdorff dimension of $E$ is greater than $d/2$, then its
distance set has positive Lebesgue measure. The recent breakthrough of Guth,
Iosevich, Ou, and Wang [7] says that in two dimensions the conclusion holds
when $\dim_{H}(E)>5/4$. In higher dimensions, the best current dimensional
thresholds are as follows:

  * •

$d=3$, Du, Guth, Ou, Wang, Wilson, and Zhang [4] (2017):
$\frac{3}{2}+\frac{3}{10}$

  * •

$d\geq 4$ even, Du, Iosevich, Ou, Wang, and Zhang [6] (2020):
$\frac{d}{2}+\frac{1}{4}$

  * •

$d\geq 5$ odd, Du and Zhang [5] (2018): $\frac{d}{2}+\frac{d}{4d-2}$

The finite field variant of this problem is known as the Erdős-Falconer
distance problem, which asks for the smallest exponent $\alpha$ such that for
any $E\subset\mathbb{F}_{q}^{d}$, if $|E|\geq q^{\alpha}$, then the distance
set covers a positive proportion of all distances. In 2005, Iosevich and
Rudnev [11] showed that if $|E|\gg q^{\frac{d+1}{2}}$, $E$ determines a
positive proportion of all distances. Unlike the continuous version, the
exponent $\frac{d+1}{2}$ has been proved to be sharp in [10] except for even
dimensions or dimensions $d\equiv 3\mod 4$ with $q\equiv 3\mod 4$. For these
cases, the conjectured exponent is $d/2$, which is in line with the Falconer
distance conjecture. Compared to the continuous version, only a few
improvements has been able to make during the last 15 years. In particular,
Chapman, Erdogan, Hart, Iosevich, and Koh [3] proved the exponent
$\frac{4}{3}$ over arbitrary finite fields, which was recently improved to
$\frac{5}{4}$ over prime fields by Murphy, Petridis, Pham, Rudnev, and Stevens
[17]. However, in higher even dimensions, we know nothing except the exponent
$(d+1)/2$. Since one of the key steps in the papers [6, 7] is a radial
projection theorem due to Orponen [20], if one wishes to adapt the methods
from $\mathbb{R}^{d}$ to $\mathbb{F}_{q}^{d}$, then a full understanding about
the radial projection over finite fields is needed. Thus, the results in this
paper provide some new progress in this direction.

An update on Conjectures 1.2 and 1.3: In a very recent paper [22], Orponen and
Shmerkin proved that Conjecture 1.2 and Conjecture 1.3 hold in two dimensions.
We refer the reader to their paper for more details and discussions.

##  2\. Notation and definitions

Here we fix notation and definitions that we use in several proofs.

For $E\subset\mathbb{F}_{q}^{d}$ and an integer $M>0$, let

$T:=\\{y\in\mathbb{F}_{q}^{d}:|\pi^{y}(E|\leq M\\}.$

For any line $\ell$, let $e(\ell)=|\ell\cap E|$, let $t(\ell)=|\ell\cap T|$,
and let $\ell(x)$ be the indicator function for $x\in\ell$. Let $L$ be the set
of lines that each contain at least one point of $T$ and at least one point of
$E$, and let $G$ be the set of all lines in $\mathbb{F}_{q}^{d}$. We also use
the notation $\binom{d}{1}_{q}$, which is defined by

$\binom{d}{1}_{q}:=\frac{q^{d}-1}{q-1}.$

Note that $\binom{d}{1}$ is the number of lines in $\mathbb{F}_{q}^{d}$ that
are incident to a specified point.

##  3\. Proofs of Theorem 1.5, Theorem 1.7, and Theorem 1.8

The proofs in this section use the Cauchy-Schwarz inequality together with the
fact that there is a unique line through each pair of distinct points.

The following lemma immediately implies Theorem 1.5, and plays an important
role in the proof of Theorem 1.8.

######  Lemma 3.1.

Let $E\subset\mathbb{F}^{d}$ be a finite set of points, let $1<C<|E|$, let $k$
be a positive integer, and let $T$ be a set of points such that

  * •

for each point $y\in T$, we have $|\pi^{y}(E)|<|E|C^{-1}$, and

  * •

for any line $\ell$, we have $|\ell\cap T|<k$.

Then,

$|T|\leq(C-1)^{-1}k|E|.$

###### Proof.

The strategy is to find upper and lower bounds on the number of triples in

$R:=\\{(y,x_{1},x_{2})\in T\times E\times E:y,x_{1},x_{2}\text{ are co-linear
and }y\notin\\{x_{1},x_{2}\\}\\}.$

Denote by $M=|E|C^{-1}$ the assumed upper bound on $\pi^{y}(E)$ for $y\in T$.
To obtain a lower bound on $|R|$, we bound the number of triples in $R$ that
contain a fixed $y\in T$:

$\sum_{\begin{subarray}{c}\ell:y\in\ell\end{subarray}}(e(\ell)-\mathbf{1}_{y\in
E})^{2}\geq
M^{-1}\left(\sum_{\begin{subarray}{c}\ell:y\in\ell\end{subarray}}(e(\ell)-\mathbf{1}_{y\in
E})\right)^{2}\geq M^{-1}(|E|-M\cdot\mathbf{1}_{y\in E})^{2}.$

Summing over all $y\in T$:

$|R|=\sum_{y\in T}\sum_{\ell:y\in\ell}(e(\ell)-\mathbf{1}_{y\in
E})^{2}\geq\sum_{y\in T}M^{-1}(|E|-M\cdot\mathbf{1}_{y\in
E})^{2}=C|T||E|-2|E||T\cap E|+M|T\cap E|.$

The upper bound relies on the observation that each pair of distinct points in
$E$ belongs to at most $k$ triples in $R$:

$\displaystyle|R|$ $\displaystyle=\sum_{x\in E}\sum_{\begin{subarray}{c}y\in
T\\\ x\neq y\end{subarray}}1+\sum_{\begin{subarray}{c}x_{1},x_{2}\in E\\\
x_{1}\neq x_{2}\end{subarray}}\sum_{\begin{subarray}{c}y\in T\\\
y\notin\\{x_{1},x_{2}\\}\end{subarray}}\sum_{\ell\in
G}\ell(x_{1})\ell(x_{2})\ell(y)$ $\displaystyle\leq|T|\,|E|-|E\cap
T|+\sum_{\begin{subarray}{c}x_{1},x_{2}\in E\\\ x_{1}\neq
x_{2}\end{subarray}}\sum_{\ell\in
G}\ell(x_{1})\ell(x_{2})\sum_{\begin{subarray}{c}y\in T\\\
y\notin\\{x_{1},x_{2}\\}\end{subarray}}\ell(y)$ $\displaystyle=|T|\,|E|-|E\cap
T|+\sum_{\begin{subarray}{c}x_{1},x_{2}\in E\\\ x_{1}\neq
x_{2}\end{subarray}}\sum_{\ell\in
G}\ell(x_{1})\ell(x_{2})(t(\ell)-\mathbf{1}_{x_{1}\in T}-\mathbf{1}_{x_{2}\in
T})$ $\displaystyle\leq|T|\,|E|-|E\cap
T|+k|E|^{2}-\sum_{\begin{subarray}{c}x_{1},x_{2}\in E\\\ x_{1}\neq
x_{2}\end{subarray}}(\mathbf{1}_{x_{1}\in T}+\mathbf{1}_{x_{2}\in T})$
$\displaystyle=|T|\,|E|-|E\cap T|+k|E|^{2}-2(|E\cap T|(|E\cap
T|-1)+(|E|-|E\cap T|)|E\cap T|)$ $\displaystyle=|T|\,|E|+k|E|^{2}-2|E|\,|E\cap
T|+|E\cap T|.$

Combining the lower and upper bounds, we get

$\displaystyle C|T|\,|E|-2|E|\,|T\cap E|+M|T\cap E|$
$\displaystyle\leq|T|\,|E|+k|E|^{2}-2|E|\,|E\cap T|+|E\cap T|,$

hence $|T|<(C-1)^{-1}k|E|$. ∎

As stated above, Lemma 3.1 immediately implies theorem 1.5.

###### Proof of Theorem 1.5.

At most $q$ points of $T$ are contained in any line in $\mathbb{F}_{q}^{d}$.
Hence, Theorem 1.5 follows from the case $k=q$ of Lemma 3.1. ∎

Next we prove Theorem 1.8. Lemma 3.1 gives a bound on $|T|$ when not too many
points of $T$ are on any single line. The next lemma bounds the number of
elements of $T$ that can be contained in a single line.

######  Lemma 3.2.

Let $\mathbb{F}$ be a field, and let $E\subset\mathbb{F}^{d}$ be a finite set
of points. Let $\ell$ be a line such that $\ell\cap E=\emptyset$. Then, for
$M<|E|/2$,

$|\ell\cap\\{y\in\mathbb{F}^{d}:|\pi^{y}(E)|\leq M\\}|\leq 2M.$

###### Proof.

Let $T$ be the set of $y\in\mathbb{F}^{d}$ such that $|\pi^{y}(E)|\leq M$ and
$L$ be the set of lines that contain at least one point of $T$ and at least
one point of $E$. Let

$R:=\\{(y,x_{1},x_{2})\in(T\cap\ell)\times E\times E:y\neq x_{1}\neq
x_{2}\text{ and }y,x_{1},x_{2}\text{ are co-linear}\\}.$

Since each ordered pair $(x_{1},x_{2})\in E^{2}$ of distinct points in $E$
determines a line that intersects $\ell$ in at most one point, we have

(10) $|R|\leq|E|(|E|-1)<|E|^{2}.$

On the other hand, we have

$\displaystyle|R|$ $\displaystyle=\sum_{y\in
T\cap\ell}\sum_{\begin{subarray}{c}\ell^{\prime}\in L\\\
y\in\ell^{\prime}\end{subarray}}e(\ell^{\prime})(e(\ell^{\prime})-1)$
$\displaystyle\geq|T\cap\ell|M^{-1}|E|^{2}-|T\cap\ell|\,|E|=|T\cap\ell||E|^{2}M^{-1}(1-M|E|^{-1})$
(11) $\displaystyle\geq 2^{-1}|T\cap\ell|\,|E|^{2}M^{-1}.$

Here, we use the Cauchy-Schwarz inequality and the fact that each point of $T$
is incident to at most $M$ lines of $L$.

The result follows directly from (10) and (11). ∎

Theorem 1.8 follows easily from Lemmas 3.1 and 3.2.

###### Proof of Theorem 1.8.

Let $\ell$ be a line. Since there are at least $|E|/2$ points of $E$ that do
not lie on $\ell$ and $M<|E|/4$, Lemma 3.2 implies that there are at most $2M$
points of $T$ contained in $\ell$. Consequently, Lemma 3.1 applied with
$C=|E|M^{-1}$ and $k=2M$ implies that

$|T|\leq(|E|M^{-1}-1)^{-1}2M|E|<4M^{2}.$

∎

###  3.1. Proof of Theorem 1.7

As promised in the introduction, the proof of Theorem 1.7 is very simple.

###### Proof of Theorem 1.7.

Let $T$ be the set of points such that $|\pi^{y}(E)|<|E|^{1/2}$, and let
$M=2^{-1}|E|^{1/2}-1$. Let $L$ be the set of lines that contain at least one
point of $T$ and at least one point of $E$.

Suppose, for contradiction, that $y,z\in T$ with $y\neq z$. Let
$L_{y},L_{z}\subset L$ be those lines of $L$ incident to $y$ and $z$,
respectively. Let $\ell_{M}$ be the line that contains both $y$ and $z$. Let
$\ell\in L_{y}\setminus\\{\ell_{M}\\}$. Then each point of $E\cap\ell$ is on a
different line of $L_{z}$, hence $|\ell\cap E|\leq M$. Since
$|L_{y}\setminus\\{\ell_{M}\\}|\leq M$, we have that $\left|\bigcup_{\ell\in
L_{y}\setminus\\{\ell_{M}\\}}(L_{y}\cap E)\right|\leq M^{2}$. Since
$M^{2}<(1/4)|E|$, it must be the case that $|\ell_{M}\cap E|>(3/4)|E|$,
contradicting our assumption. ∎

##  4\. Proofs of Theorems 1.1 and 1.4

The proofs in this section use the Cauchy-Schwarz inequality together with
several combinatorial properties of points and lines in $\mathbb{F}_{q}^{d}$.
In particular, each point is incident to $\binom{d}{1}_{q}$ lines, each line
is incident to $q$ points, and $\mathbb{F}_{q}^{d}$ has $q^{d}$ points in
total.

The proofs of Theorems 1.1 and 1.4 are similar. The basic plan of both proofs
is to give upper and lower bounds on $\sum_{\ell\in L}e(\ell)t(\ell)$.

We use the same simple lower bound for both proofs. Each pair $(x,y)\in
E\times T$ is contained in exactly one line of $L$ if $x\neq y$, and at least
one line of $L$ if $x=y$. Hence,

(12) $\sum_{\ell\in L}e(\ell)t(\ell)\geq|E|\,|T|.$

The upper bounds on $\sum_{\ell\in L}e(\ell)t(\ell)$ used in the two proofs of
this section rely on different arguments, but both are inspired by work on
incidence bounds for large sets in finite space. These bounds were first
investigated by Haemmers [9], and have had many recent applications to
problems in arithmetic combinatorics and Erdős-type questions over finite
vector spaces [1, 2, 19, 23, 24].

The following lemma and its proof is nearly identical to Lemma 1 in [18].

######  Lemma 4.1.

Let $E\subset\mathbb{F}_{q}^{d}$. Then,

(13) $\displaystyle\sum_{\ell\in
G}e(\ell)^{2}=\binom{d}{1}_{q}|E|+|E|(|E|-1),\text{ and}$ (14)
$\displaystyle\sum_{\ell\in
G}(e(\ell)-|E|q^{1-d})^{2}\leq\binom{d}{1}_{q}|E|.$

###### Proof.

The following calculation yields (13):

$\displaystyle\sum_{\ell\in G}e(\ell)^{2}$ $\displaystyle=\sum_{\ell\in
G}\sum_{(x,x^{\prime})\in E^{2}}\ell(x)\ell(x^{\prime})$
$\displaystyle=\sum_{\ell}\sum_{x\in
E}\ell(x)+\sum_{\ell}\sum_{\begin{subarray}{c}(x,x^{\prime})\in E^{2}:\\\
x\neq x^{\prime}\end{subarray}}\ell(x)\ell(x^{\prime})$
$\displaystyle=\binom{d}{1}_{q}|E|+|E|(|E|-1).$

In the third line, we use the facts that each point is incident to exactly
$\binom{d}{1}_{q}$ lines, and each pair of distinct points is contained in
exactly one line.

We now show that (14) follows from (13). Indeed,

$\displaystyle\sum_{\ell\in G}(e(\ell)-|E|q^{-(d-1)})^{2}$
$\displaystyle=\sum_{\ell\in G}e(\ell)^{2}-2|E|q^{-(d-1)}\sum_{\ell\in
G}e(\ell)+|G||E|^{2}q^{-2(d-1)}$ $\displaystyle=\sum_{\ell\in
G}e(\ell)^{2}-q^{-(d-1)}\binom{d}{1}_{q}|E|^{2}$
$\displaystyle<\binom{d}{1}_{q}|E|.$

In the second line, we use the facts that each point is incident to exactly
$\binom{d}{1}_{q}$ lines, and that $|G|=q^{d-1}\binom{d}{1}_{q}$. ∎

###  4.1. Proof of Theorem 1.1

First we obtain an upper bound on $\sum_{\ell\in L}e(\ell)t(\ell)$.

######  Lemma 4.2.

We have

(15) $\sum_{\ell\in
L}e(\ell)t(\ell)\leq(Mq^{-(d-1)})|E|\,|T|+\sqrt{(M|T|+|T|^{2})|E|\binom{d}{1}_{q}}.$

###### Proof.

Since each point of $T$ is incident to at most $M$ lines of $L$, we have
$\sum_{\ell\in L}t(\ell)\leq M|T|$, and hence

$\displaystyle\sum_{\ell\in L}e(\ell)t(\ell)$
$\displaystyle\leq\frac{M|E|\,|T|}{q^{d-1}}+\sum_{\ell\in
L}t(\ell)\left(e(\ell)-|E|q^{-(d-1)}\right)$
$\displaystyle\leq\frac{M|E|\,|T|}{q^{d-1}}+\sqrt{\sum_{\ell\in
L}t(\ell)^{2}\cdot\sum_{\ell\in L}\left(e(\ell)-|E|q^{-(d-1)}\right)^{2}}$
(16) $\displaystyle\leq\frac{M|E|\,|T|}{q^{d-1}}+\sqrt{\sum_{\ell\in
L}t(\ell)^{2}\cdot\sum_{\ell\in G}\left(e(\ell)-|E|q^{-(d-1)}\right)^{2}}.$

Lemma 4.1 provides an upper bound for $\sum_{\ell\in
G}\left(e(\ell)-|E|q^{-(d-1)}\right)^{2}$, so we only need to bound
$\sum_{\ell\in L}t(\ell)^{2}$.

$\displaystyle\sum_{\ell\in L}t(\ell)^{2}$ $\displaystyle=\sum_{\ell\in
L}\sum_{(y,y^{\prime})\in T^{2}}\ell(y)\ell(y^{\prime})$
$\displaystyle=\sum_{\ell\in
L}t(\ell)+\sum_{\ell}\sum_{\begin{subarray}{c}(y,y^{\prime})\in T^{2}:\\\
y\neq y^{\prime}\end{subarray}}\ell(y)\ell(y^{\prime})$ (17)
$\displaystyle\leq M|T|+|T|(|T|-1)<M|T|+|T|^{2}.$

Combining (17) with the bound $\sum_{\ell\in
G}\left(e(\ell)-|E|q^{-(d-1)}\right)^{2}\leq|E|\binom{d}{1}_{q}$ given by
Lemma 4.1 and (16) completes the proof. ∎

We use Lemma 4.2 to prove the following, which is slightly more general than
Theorem 1.1.

######  Theorem 4.3.

Let $E\subset\mathbb{F}_{q}^{d}$ and let $M$ be a positive integer. Let
$a=\binom{d}{1}_{q}|E|^{-1}$ and let $b=Mq^{1-d}$. Let
$C=(1-2b+b^{2}-a)^{-1}$. If $C>0$, then

(18) $\\#\\{y\in\mathbb{F}_{q}^{d}\colon|\pi^{y}(E)|\leq
M\\}<C\binom{d}{1}_{q}M|E|^{-1}.$

###### Proof.

Combining the lower bound (12) with the upper bound (15) from Lemma 4.2 leads
quickly to the conclusion of the theorem:

$\displaystyle(1-2b+b^{2})|E|^{2}|T|^{2}$
$\displaystyle=(1-Mq^{-(d-1)})^{2}|E|^{2}|T|^{2}$
$\displaystyle<(M|T|+|T|^{2})|E|\binom{d}{1}_{q}$
$\displaystyle=M|T|\binom{d}{1}_{q}+a|E|^{2}|T|^{2}.$

Hence,

$|T|<C\binom{d}{1}_{q}M|E|^{-1},$

as claimed. ∎

###### Proof of Theorem 1.1.

Apply Theorem 4.3 with $a=3^{-1}$ and $b=4^{-1}$. ∎

###  4.2. Proof of Theorem 1.4

To prove Theorem 1.4, we first need a refinement of Lemma 4.2.

######  Lemma 4.4.

Let $a=|E|q^{1-d}$, let $b=M|E|^{-1}$, and let $c=\sqrt{(1-b)/a}$. If
$(1-b)/a>1$, then

$\sum_{\ell\in
L}e(\ell)t(\ell)<(b+ac)|E|\,|T|+(1-c^{-1})^{-1}|E|\sqrt{2\binom{d}{1}_{q}|T|}.$

###### Proof.

We divide the sum $\sum_{\ell\in L}e(\ell)t(\ell)$ into three parts:

$\sum_{\ell\in
L}e(\ell)t(\ell)=\sum_{\ell:e(\ell)=1}e(\ell)t(\ell)+\sum_{\begin{subarray}{c}\ell:e(\ell)\geq
2,\\\ t(\ell)\leq
c|T|q^{1-d}\end{subarray}}e(\ell)t(\ell)+\sum_{\begin{subarray}{c}\ell:e(\ell)\geq
2,\\\ t(\ell)>c|T|q^{1-d}\end{subarray}}e(\ell)t(\ell).$

Bounding the first two terms is easy:

(19) $\sum_{\ell:e(\ell)=1}t(\ell)\leq\sum_{y\in T}|\pi^{y}(E)|\leq
M|T|=b|T|\,|E|,$ (20) $\sum_{\begin{subarray}{c}\ell:e(\ell)\geq 2,\\\
t(\ell)\leq c|T|q^{1-d}\end{subarray}}e(\ell)t(\ell)\leq
c|T|q^{1-d}\sum_{\ell:e(\ell)\geq 2}e(\ell)<c|T|q^{1-d}|E|^{2}=ac|T|\,|E|.$

Let $L^{\prime}=\\{\ell\in L:e(\ell)\geq 2,t(\ell)>c|T|q^{1-d}\\}$. We have

(21) $\left(\sum_{\ell\in
L^{\prime}}e(\ell)t(\ell)\right)^{2}\leq\sum_{\ell\in
L^{\prime}}t(\ell)^{2}\sum_{\ell\in L^{\prime}}e(\ell)^{2}.$

We use the lower bound on $t(\ell)$ together with Lemma 4.1 to bound
$\sum_{\ell\in L^{\prime}}t(\ell)^{2}$. Denote $d=(1-c^{-1})^{-2}$. Note that

$d^{-1}t(\ell)^{2}=(t(\ell)-c^{-1}t(\ell))^{2}\leq(t(\ell)-|T|q^{1-d})^{2}.$

Together with (14) of Lemma 4.1, this yields

(22) $\sum_{\ell\in L^{\prime}}t(\ell)^{2}=d\sum_{\ell\in
L^{\prime}}d^{-1}t(\ell)^{2}\leq d\sum_{\ell\in
L^{\prime}}(t(\ell)-|T|q^{1-d})^{2}<(1-c^{-1})^{-2}\binom{d}{1}_{q}|T|.$

To bound $\sum_{\ell\in L^{\prime}}e(\ell)^{2}$, we use the fact that each
point of $E$ is incident to fewer than $|E|$ lines of $L^{\prime}$ to infer

(23) $\sum_{\ell\in L^{\prime}}e(\ell)^{2}<2|E|^{2},$

Taken together, (21), (22), and (23) imply

(24) $\left(\sum_{\ell\in
L^{\prime}}e(\ell)t(\ell)\right)^{2}\leq\sum_{\ell\in
L^{\prime}}t(\ell)^{2}\sum_{\ell\in
L^{\prime}}e(\ell)^{2}<2(1-c^{-1})^{-2}\binom{d}{1}_{q}|T|\,|E|^{2}.$

Combining (19), (20), and (24) leads immediately to the claimed conclusion. ∎

We remark that a very similar proof leads to a bound analogous to 3. The key
idea that leads to our stronger result is to use the trivial bound 23 instead
of Lemma 4.1 to bound $\sum_{\ell\in L^{\prime}}e(\ell)^{2}$.

We use Lemma 4.4 to obtain the following, which is slightly stronger than
Theorem 1.4.

######  Theorem 4.5.

Let $E\subset\mathbb{F}_{q}^{d}$ and let $M$ be a positive integer. Let
$a=|E|q^{1-d}$, and let $b=M|E|^{-1}$. Let $c=\sqrt{(1-b)/a}$. Then,

$\\#\\{y\in\mathbb{F}_{q}^{d}:|\pi^{y}(E)|\leq
M\\}<2(1-b-ac)^{-2}(1-c^{-1})^{-2}\binom{d}{1}_{q}.$

###### Proof.

Lemma 4.4 and (12) together imply

$|T|\,|E|<(b+ac)|T|\,|E|+(1-c^{-1})^{-1}|E|\sqrt{2\binom{d}{1}_{q}|T|},$

which easily implies the claimed bound on $|T|$. ∎

###### Proof of Theorem 1.4.

Apply Theorem 4.5 with $a=100^{-1}$ and $b=10^{-1}$. ∎

##  5\. Proofs Theorems 1.9 and 1.10

The proofs in this section are less elementary than those in the previous
sections, and rely on incidence bounds. The two proofs are identical in
outline, but the calculations are simpler over the reals.

###  5.1. Over the reals

To proceed, we need to recall the following celebrated Szemerédi-Trotter
theorem and one of its consequence on the number of $k$-rich lines.

######  Theorem 5.1 ([29]).

Let $E$ be a set of points and $L$ be a set of lines in $\mathbb{R}^{2}$.
Then,

(25) $\sum_{\ell\in L}e(\ell)=O(|E|^{2/3}|L|^{2/3}+|E|+|L|).$

Let $L_{\geq k}$ be the set of $k$-rich lines, i.e. lines with at least $k$
points from $E$, then

(26) $|L_{\geq k}|=O(|E|^{2}k^{-3}+|E|k^{-1}).$

The following is a standard consequence, we include a proof for the reader’s
convenience.

######  Lemma 5.2.

There exist positive constants $c_{1},c_{2}$ such that, for any set $E$ of
points in $\mathbb{R}^{2}$,

(27) $\sum_{c_{1}\leq k\leq c_{2}|E|}k^{2}|L_{=k}|<10^{-1}|E|^{2}.$

###### Proof.

$\displaystyle\sum_{c_{1}\leq k\leq c_{2}|E|}k^{2}|L_{=k}|$
$\displaystyle=\sum_{c_{1}\leq k\leq c_{2}|E|}k^{2}(|L_{\geq k}|-|L_{\geq
k+1}|)$ $\displaystyle=\sum_{c_{1}\leq k\leq c_{2}|E|}k^{2}|L_{\geq
k}|-\sum_{c_{1}+1\leq k\leq c_{2}|E|+1}(k-1)^{2}|L_{\geq k}|$
$\displaystyle=\sum_{c_{1}\leq k\leq
c_{2}|E|}(k^{2}-(k-1)^{2})|L_{=k}|+c_{1}^{2}|L_{=c_{1}}|-(c_{2}|E|)^{2}|L_{=c_{2}|E|+1}|$
$\displaystyle\leq\sum_{c_{1}\leq k\leq
c_{2}|E|-1}kO(|E|^{2}k^{-3}+|E|k^{-1})+O(c_{1}^{-1}|E|^{2})$
$\displaystyle\leq\sum_{c_{1}\leq k}O(|E|^{2}k^{-2})+\sum_{k\leq
c_{2}|E|}O(|E|)+O(c_{1}^{-1}|E|^{2})$ $\displaystyle\leq
O(c_{1}^{-1}|E|^{2})+O(c_{2}|E|^{2}).$

No matter what the constants hidden in the $O$-notation are, there are choices
for $c_{1}$ and $c_{2}$ so that the right side is bounded by $10^{-1}|E|^{2}$,
as claimed. ∎

######  Theorem 5.3.

Let $c_{1}$ and $c_{2}$ be as in Lemma 5.2. There exists a constant
$0<c_{3}<1$ such that the following holds. For any finite
$E\subset\mathbb{R}^{2}$ such that $|\ell\cap E|<c_{2}|E|$ for each line
$\ell$ and $M\leq c_{3}|E|$, we have

$\\#\\{y\in\mathbb{R}^{2}:\pi^{y}(E)<M\\}<O(M^{2}E^{-1}).$

###### Proof.

As before, we proceed by bounding the sum $\sum_{\ell\in L}e(\ell)t(\ell)$
from above and below. We use the same lower bound $\sum_{\ell\in
L}e(\ell)t(\ell)\geq|E|\,|T|$ as before. For the upper bound, we partition the
sum as follows:

(28) $\sum_{\ell\in L}e(\ell)t(\ell)\leq\sum_{\begin{subarray}{c}\ell\in L:\\\
e(\ell)<c_{1}\end{subarray}}e(\ell)t(\ell)+\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)t(\ell)+\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq c_{1},t(\ell)=1\end{subarray}}e(\ell)t(\ell).$

Bounding the first term: This is easy, namely,

$\sum_{\begin{subarray}{c}\ell\in L:\\\
e(\ell)<c_{1}\end{subarray}}e(\ell)t(\ell)=\sum_{y\in
T}\sum_{\begin{subarray}{c}\ell\in L:\\\
y\in\ell\end{subarray}}e(\ell)<c_{1}|M|\,|T|\leq c_{1}c_{3}|E|\,|T|.$

Bounding the second term: By the Cauchy-Schwarz inequality,

(29) $\left(\sum_{\begin{subarray}{c}\ell\in L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)t(\ell)\right)^{2}\leq\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)^{2}\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq c_{1},t(\ell)>1\end{subarray}}t(\ell)^{2}.$

Lemma 5.2 bounds the first sum on the right side by $10^{-1}|E|^{2}$. To bound
the second sum, we use the observation that each point of $T$ is incident to
fewer than $T$ lines $\ell$ such that $t(\ell)>1$:

$\displaystyle\sum_{\begin{subarray}{c}\ell\in L:\\\
t(\ell)>1\end{subarray}}t(\ell)^{2}$ $\displaystyle=\sum_{\ell\in
L}\sum_{y_{1}\neq y_{2}\in T}\ell(y_{1})\ell(y_{2})+\sum_{\ell\in L}\sum_{y\in
T}\ell(y)$ $\displaystyle=|T|(|T|-1)+\sum_{y\in T}\sum_{\ell\in L}\ell(y)$
$\displaystyle\leq|T|(|T|-1)+\sum_{y\in T}|T|<2|T|^{2}.$

Combining these leads to

$\sum_{\begin{subarray}{c}\ell\in L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)t(\ell)\leq 5^{-1/2}|E|\,|T|.$

Bounding the third term: The key observation is that

$\\#\\{\ell\in L:t(\ell)=1\\}\leq M|T|.$

Combined with the Szemerédi-Trotter theorem 5.1, one has

$\sum_{\begin{subarray}{c}\ell\in L:\\\ e(\ell)\geq
c_{1},t(\ell)=1\end{subarray}}e(\ell)t(\ell)\leq\sum_{\begin{subarray}{c}\ell\in
L:\\\ t(\ell)=1\end{subarray}}e(\ell)=O((M|T|\,|E|)^{2/3}+M|T|+|E|).$

Combining the upper and lower bounds gives

$|E|\,|T|\leq(c_{1}\,c_{3}+5^{-1/2})|E|\,|T|+O((M|E|\,|T|)^{2/3}+c_{3}|E|\,|T|+|E|).$

By choosing $c_{3}$ sufficiently small, we have

$|E|\,|T|=O((M|E|\,|T|)^{2/3}),$

which leads directly to the desired conclusion. ∎

###  5.2. Over prime fields

In the prime field setting, we make use of a variant of the Stevens-De Zeeuw
point-line incidence bound in [12, Theorem 14].

######  Theorem 5.4 ([28]).

Let $P$ be a point set in $\mathbb{F}_{p}^{2}$ and $L$ be a set of lines in
$\mathbb{F}_{p}^{2}$. If $|P|\leq p^{8/5}$, then

$\sum_{\ell\in L}e(\ell)=O(|P|^{11/15}|L|^{11/15}+|P|+|L|).$

Let $L_{\geq k}$ be the set of $k$-rich lines, i.e. lines with at least $k$
points from $P$, then

$|L_{\geq k}|=O(|P|^{11/4}k^{-\frac{15}{4}}+|P|k^{-1}).$

We also have an analog of Lemma 5.2.

######  Lemma 5.5.

There exists a positive constant $c$ such that, for any set $E$ of points in
$\mathbb{R}^{2}$,

(30) $\sum_{c^{-4/7}|E|^{3/7}\leq k\leq c|E|}k^{2}|L_{=k}|<10^{-1}|E|^{2}.$

###### Proof.

Set $c_{1}:=c^{-4/7}|E|^{3/7}$.

$\displaystyle\sum_{c_{1}\leq k\leq c|E|}k^{2}|L_{=k}|$
$\displaystyle=\sum_{c_{1}\leq k\leq c|E|}k^{2}(|L_{\geq k}|-|L_{\geq k+1}|)$
$\displaystyle=\sum_{c_{1}\leq k\leq c|E|}k^{2}|L_{\geq k}|-\sum_{c_{1}+1\leq
k\leq c|E|+1}(k-1)^{2}|L_{\geq k}|$ $\displaystyle=\sum_{c_{1}\leq k\leq
c|E|}(k^{2}-(k-1)^{2})|L_{=k}|+c_{1}|L_{=c_{1}}|-(c|E|)^{2}|L_{=c|E|+1}|$
$\displaystyle\leq\sum_{c_{1}\leq k\leq
c|E|-1}kO(|E|^{11/4}k^{-15/4}+|E|k^{-1})+O(c_{1}^{-7/4}|E|^{11/4})+O(c_{1}|E|)$
$\displaystyle\leq\sum_{c_{1}\leq k}O(|E|^{11/4}k^{-7/4})+\sum_{k\leq
c_{2}|E|}O(|E|)+O(c_{1}^{-1}|E|^{2})$ $\displaystyle\leq
O(c_{1}^{-7/4}|E|^{11/4})+O(c_{1}|E|)+O(c|E|^{2}).$

So we can choose $c$ small enough, so that the right side is bounded by
$10^{-1}|E|^{2}$. ∎

###### Proof of Theorem 1.10.

Our argument is similar to that over the reals, for the sake of completeness,
we reproduce all details here.

As above, we want to bound the sum $\sum_{\ell\in L}e(\ell)t(\ell)$ from above
and below. We have $\sum_{\ell\in L}e(\ell)t(\ell)\geq|E|\,|T|$. For the upper
bound, we partition the sum as follows:

(31) $\sum_{\ell\in L}e(\ell)t(\ell)\leq\sum_{\begin{subarray}{c}\ell\in L:\\\
e(\ell)<c_{1}\end{subarray}}e(\ell)t(\ell)+\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)t(\ell)+\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq c_{1},t(\ell)=1\end{subarray}}e(\ell)t(\ell),$

where $c_{1}:=c^{-4/7}|E|^{3/7}$.

Bounding the first term: This is easy, namely,

$\sum_{\begin{subarray}{c}\ell\in L:\\\
e(\ell)<c_{1}\end{subarray}}e(\ell)t(\ell)=\sum_{y\in
T}\sum_{\begin{subarray}{c}\ell\in L:\\\
y\in\ell\end{subarray}}e(\ell)<c_{1}|M|\,|T|\leq c|E|\,|T|.$

Bounding the second term: By the Cauchy-Schwarz inequality,

(32) $\left(\sum_{\begin{subarray}{c}\ell\in L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)t(\ell)\right)^{2}\leq\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)^{2}\sum_{\begin{subarray}{c}\ell\in
L:\\\ e(\ell)\geq c_{1},t(\ell)>1\end{subarray}}t(\ell)^{2}.$

Lemma 5.5 bounds the first sum on the right side by $10^{-1}|E|^{2}$. To bound
the second sum, we use the observation that each point of $T$ is incident to
fewer than $T$ lines $\ell$ such that $t(\ell)>1$:

$\displaystyle\sum_{\begin{subarray}{c}\ell\in L:\\\
t(\ell)>1\end{subarray}}t(\ell)^{2}$ $\displaystyle=\sum_{\ell\in
L}\sum_{y_{1}\neq y_{2}\in T}\ell(y_{1})\ell(y_{2})+\sum_{\ell\in L}\sum_{y\in
T}\ell(y)$ $\displaystyle=|T|(|T|-1)+\sum_{y\in T}\sum_{\ell\in L}\ell(y)$
$\displaystyle\leq|T|(|T|-1)+\sum_{y\in T}|T|<2|T|^{2}.$

Combining these leads to

$\sum_{\begin{subarray}{c}\ell\in L:\\\ e(\ell)\geq
c_{1},t(\ell)>1\end{subarray}}e(\ell)t(\ell)\leq 5^{-1/2}|E|\,|T|.$

Bounding the third term: The key observation is that

$\\#\\{\ell\in L:t(\ell)=1\\}\leq M|T|.$

Combined with the Theorem 5.4, one has

$\sum_{\begin{subarray}{c}\ell\in L:\\\ e(\ell)\geq
c_{1},t(\ell)=1\end{subarray}}e(\ell)t(\ell)\leq\sum_{\begin{subarray}{c}\ell\in
L:\\\
t(\ell)=1\end{subarray}}e(\ell)=O((M|T|\,|E|)^{11/15}+M|T|+|E|)=O\left((M|T|\,|E|)^{11/15}+|E|\right)+\frac{|T|\,|E|}{10}.$

Combining the upper and lower bounds gives

$|E|\,|T|\leq(c+5^{-1/2})|E|\,|T|+O\left((M|T|\,|E|)^{11/15}+|E|\right)+\frac{|T|\,|E|}{10}.$

By choosing $c$ sufficiently small, we have

$|E|\,|T|=O((M|E|\,|T|)^{11/15}),$

which leads directly to the desired conclusion.

∎

##  6\. Acknowledgements

We would like to thank Bochen Liu and Tuomas Orponen for many discussions
about the results in the continuous setting.

B. Lund was supported by the Institute for Basic Science (IBS-R029-C1). T.
Pham would like to thank to the VIASM for the hospitality and for the
excellent working condition.

## References

  * [1] E. Aksoy Yazici, B. Murphy, M. Rudnev and I. Shkredov, Growth estimates in positive characteristic via collisions, International Mathematics Research Notices, 2017(23) (2017), 7148-7189.
  * [2] M. Bennett, A. Iosevich and J. Pakianathan, Three-point configurations determined by subsets of $\mathbb{F}_{q}^{2}$ via the Elekes-Sharir Paradigm, Combinatorica, 34(6) (2014): 689–706.
  * [3] J. Chapman, M. Burak Erdoğan, D. Hart, A. Iosevich and D. Koh, Pinned distance sets, $k$-simplices, Wolff’s exponent in finite fields and sum-product estimates, Mathematische Zeitschrift, 271(1) (2012), 63–93.
  * [4] X. Du, L. Guth, Y. Ou, H. Wang, B. Wilson and R. Zhang, Weighted restriction estimates and application to Falconer distance set problem, American Journal of Mathematics, 143(1) (2021), 175–211.
  * [5] X. Du and R. Zhang, Sharp $L^{2}$\- estimates of the Schrödinger maximal function in higher dimensions, Annal of Mathematics, 189 (2019), no. 3, 837–861.
  * [6] X. Du, A. Iosevich, Y. Ou, H. Wang and R. Zhang, An improved result for Falconer’s distance set problem in even dimensions, Mathematische Annalen, 380(3) (2021), 1215–1231.
  * [7] L. Guth, A. Iosevich, Y. Ou and H. Wang, On Falconer’s distance set problem in the plane, Inventiones mathematicae, 219(3), 779–830.
  * [8] B. Hanson, B. Lund and O. Roche-Newton, On distinct perpendicular bisectors and pinned distances in finite fields, Finite Fields and Their Applications, 37 (2016): 240–264.
  * [9] W.H. Haemers, Eigenvalue techniques in design and graph theory, Number 121, Mathematisch centrum Amsterdam, 1980.
  * [10] D. Hart, A. Iosevich, and D. Koh, M. Rudnev, _Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdös-Falconer distance conjecture_ , Transactions of the American Mathematical Society, 363(6) (2011), 3255–3275.
  * [11] A. Iosevich, and M. Rudnev, Erdős distance problem in vector spaces over finite fields, Transactions of the American Mathematical Society, 359(12) (2007): 6127–6142.
  * [12] B. Lund, G. Petridis, Bisectors and pinned distances, Discrete and Computational Geometry, 64(3) (2020): 995–1012.
  * [13] B. Liu, On hausdorff dimension of radial projections, Revista Matemática Iberoamericana, 37(4) (2020): 1307–1319.
  * [14] B. Liu and C-Y. Shen, Intersection between pencils of tubes, discretized sum-product, and radial projections, arXiv:2001.02551 (2020).
  * [15] P. Mattila,  Hausdorff dimension, projections, and the Fourier transform,  Publicacions Matematiques, 48(1) (2004), 3–48.
  * [16] P. Mattila and T. Orponen,  Hausdorff dimension, intersections of projections and exceptional plane sections,  Proceedings of the American Mathematical Society, 144(8) (2016):3419–3430.
  * [17] B. Murphy, G. Petridis, T. Pham, M. Rudnev and S. Stevens, On the pinned distances problem over finite fields, Journal of London Mathematical Society, 105(1) (2022): 469-499.
  * [18] B. Murphy, G. Petridis, A point-line incidence identity in finite fields, and applications, Moscow Journal of Combinatorics and Number Theory, 2016.
  * [19] B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev and I. D. Shkredov, New results on sum-product type growth over fields, Mathematika, 65(3) (2019), 588–642.
  * [20] T. Orponen, On the dimension and smoothness of radial projections, Analysis and PDE, 12(5):1273–1294, 2019.
  * [21] T. Orponen, A sharp exceptional set estimate for visibility, Bulletin of the London Mathematical Society, 50(1) (2018):1–6.
  * [22] T. Orponen and P. Shmerkin, On exceptional sets of radial projections, arXiv:2205.13890 (2022).
  * [23] M. Rudnev and I. D. Shkredov, On growth rate in $SL_{2}(F_{p})$, the affine group and sum product type implications, arXiv:1812.01671 (2018).
  * [24] O. Roche-Newton, M. Rudnev and I. D. Shkredov, New sum-product type estimates over finite fields, Advances in Mathematics, 293 (2016), 589–605.
  * [25] Y. Peres and W. Schlag, Smoothness of projections, Bernoulli convolutions, and the dimension of exceptions, Duke Mathematical Journal, 102(2):193–251, 2000.
  * [26] P. Shmerkin, A nonlinear version of Bourgain’s projection theorem, accepted in Journal of European Mathematical Society (2022).
  * [27] P. Shmerkin and H. Wang, On the distance sets spanned by sets of dimension $d/2$ in $\mathbb{R}^{d}$, arXiv:2112.09044 (2021).
  * [28] S. Stevens and F. De Zeeuw, An improved point-line incidence bound over arbitrary fields, Bulletin of the London Mathematical Society, 49(5) (2017): 842–858.
  * [29] E. Szemerédi and W.T. Trotter, Extremal problems in discrete geometry, Combinatorica, 3(3):381–392, 1983.