# The extensible No-Three-In-Line problem

Dániel T. Nagy Alfréd Rényi Institute of Mathematics. The author is partially
supported by NKFIH grants FK 132060 and PD 137779 and by the János Bolyai
Research Fellowship of the Hungarian Academy of Sciences. E-mail:
<EMAIL_ADDRESS>Zoltán Lóránt Nagy ELTE Linear Hypergraphs Research Group
and ELTE GAC Research Group, Eötvös Loránd University, Budapest, Hungary. The
author is supported by the Hungarian Research Grant (NKFI) PD 134953 and K
124950. E-mail<EMAIL_ADDRESS>Russ Woodroofe University of Primorska,
Koper, Slovenia. The author is supported in part by the Slovenian Research
Agency (ARRS) research program P1-0285 and research projects J1-9108, N1-0160,
J1-2451, and J3-3003. E-mail<EMAIL_ADDRESS>Webpage:
https://osebje.famnit.upr.si/~russ.woodroofe/

###### Abstract

The classical No-Three-In-Line problem seeks the maximum number of points that
may be selected from an $n\times n$ grid while avoiding a collinear triple.
The maximum is well known to be linear in $n$. Following a question of Erde,
we seek to select sets of large density from the infinite grid
$\mathbb{Z}^{2}$ while avoiding a collinear triple. We show the existence of
such a set which contains $\Theta(n/\log^{1+\varepsilon}n)$ points in
$[1,n]^{2}$ for all $n$, where $\varepsilon>0$ is an arbitrarily small real
number. We also give computational evidence suggesting that a set of lattice
points may exist that has at least $n/2$ points on every large enough $n\times
n$ grid.

Keywords: no-three-in-line, collinear triples, square lattice

##  1 Introduction

A set of points in the plane are said to be in _general position_ if no three
of the points lie on a common line. Motivated by a problem concerning the
placement of chess pieces, Dudeney [9] asked how many points may be placed in
an $n\times n$ grid so that the points are in general position. This No-Three-
In-Line problem has received considerable attention: for history and
background, we refer to the book of Brass, Moser, and Pach [8] and that of
Eppstein [10]; see also [17] for the problem in a higher dimensional setting.
For an upper bound, it is straightforward to see that at most $2n$ points may
so be placed. For rather small $n$, several examples have been constructed
where the theoretical bound $2n$ can be attained, see e.g. [3, 11]. However,
it is still an open problem to determine the answer for large $n$.

Joshua Erde proposed the following question at the Third Southwestern German
Workshop on Graph Theory.

######  Question 1.1.

Suppose that $S\subseteq\mathbb{Z}^{2}$ is a set of grid points in general
position. Is it true that

$\lim\inf\frac{\left|S\cap[1,n]^{2}\right|}{n}=0?$

The purpose of this paper is to give evidence suggesting that the answer to
the question may be “no”.

While it is unknown for larger $n$ whether the upper bound $2n$ is achievable
in the $n\times n$ grid, there are several constructions where the size of the
set is a smaller multiple of $n$. The earliest of these is due to Erdős
(appearing in a paper published by Roth [18]), and uses the _modular parabola_
, consisting of the points $(i,i^{2})\mod p$. If $n=p$ is a prime number, then
this yields $n$ points in general position in $\mathbb{Z}^{2}\cap[1,n]^{2}$.
If $n$ is not prime, then taking $p$ to be the largest prime before $n$ yields
$n-o(n)$ points in general position.

The best known general construction for the No-Three-In-Line problem is due to
Hall, Jackson, Sudbery, and Wild [13]. Their construction places points on a
hyperbola $xy=k\pmod{p}$, where $p$ is a prime slightly smaller than $n/2$,
and yields $\frac{3}{2}n-o(n)$ points in general position.

Related problems in projective geometry are also of importance. For a given
set of points, a line is called a secant if it intersects the point set in at
least two points. Point sets having no secants of size larger than $2$ are
called arcs. Following earlier work of Bose [7], Segre showed that for odd
$q$, every arc of $q+1$ points in Desarguesian projective geometry $PG(2,q)$
is a conic [20] (see also [19]). Arcs and higher dimensional analogues have
abundant applications in cryptography and coding theory [5, 6]. There are also
connections between the No-Three-In-Line problem and planar drawings of graphs
[22].

Our aim in this paper is to give a bound on the growth rate of
$|S\cap[1,n]^{2}|$. Thus, in contrast with the finite grid case, we need $S$
to be dense in every square $[1,n]^{2}$.

A trivial lower bound follows from the parabola construction
$\\{(x,x^{2}):x\in\mathbb{Z}^{+}\\}$, giving

$|S\cap[1,n]^{2}|=\Omega(n^{1/2}).$

The constructions of Erdős and of Hall, Jackson, Sudbery, and Wild give large
point sets in general position in any $n\times n$ grid, but rely heavily on
choosing a prime based on $n$. These constructions do not straightforwardly
generalize to an infinite set, as required for Question 1.1. Payne and Wood in
[16] give a probabilistic construction (which can be turned into a
probabilistic algorithm, as observed in [10, Algorithm 9.22]), but their
techniques also rely on $n$ being fixed.

Thus, Question 1.1 asks whether there are large sets of points in general
position in the $n\times n$ grid, which can be extended nicely to larger sets
of such points in larger grids (the _Extensible No-Three-In-Line problem_ of
the title). This is connected closely to greedy approaches to the No-Three-In-
Line problem, in which one seeks to build a large set of points in general
position by adding points one-by-one according to some simple rubric. Although
greedy approaches often appear to work reasonably well at building large point
sets in computer experiments, they do not seem to be easy to analyze.

A subset $S$ in general position of points from some universe $U$ is said to
be _saturated_ if the addition of any further point from $U$ destroys the
general position property. As greedy algorithms often add points until no more
points can be added, they may result in saturated subsets in general position.
Saturated subsets were considered by Adena, Holton, and Kelly in [1], and
Martin Gardner asked a related question in his “Mathematical Games” column
[12]. It is straightforward to see that any saturated subset has at least
$\Omega(\sqrt{n})$ points.

Recently, Aichholzer, Eppstein, and Hainzl found a significantly improved
lower bound on saturated subsets.

######  Theorem 1.2 (Aichholzer, Eppstein, and Hainzl [2]).

If $S$ is a saturated subset of points in general position from an $n\times n$
grid, then $\left|S\right|=\Omega(n^{2/3})$.

It follows straightforwardly that there is an infinite subset
$S\subseteq\mathbb{Z}^{2}$ in general position so that
$\left|S\cap[1,n]^{2}\right|=\Omega(n^{2/3})$. It is worth remarking that the
result of Theorem 1.2 is markedly different from the situation in a projective
plane: for any sufficiently large projective plane having $q^{2}+q+1$ points,
Kim and Vu [15] showed that there is a saturated (or maximal) arc of order
$\sqrt{q}\cdot\log^{c}q$ (for some fixed $c$). This indicates that completing
a given structure to gain a dense set in a larger square is difficult in
general.

We show that the asymptotic growth of the size of the point set for the
problem on the infinite grid can, in fact, be almost linear.

######  Theorem 1.3.

For any $\varepsilon>0$, it is possible to construct a set
$S\subseteq\mathbb{Z}^{2}$ of grid points in general position with

$\left|S\cap[1,n]^{2}\right|=\Theta(n/\log^{1+\varepsilon}n).$

In particular, it holds that

$\lim\inf\frac{\left|S\cap[1,n]^{2}\right|}{n/\log^{1+\varepsilon}n}>0.$

The main ingredients of the construction underlying Theorem 1.3 are as
follows. We place separated copies of the parabola construction of Erdős along
the curve $x/\log^{\varepsilon}x$. Specifically, for each value $x=2^{n}$, we
consider a square placed near the point $(2^{n},n^{\varepsilon})$ having side
length a small multiple of $2^{n}/n^{1+\varepsilon}$. We choose a suitable
prime $p_{n}$ for each integer $n$, and place a translated copy of Erdős’s
parabola construction with respect to $p_{n}$ in the square. Finally, we
delete those points from each such parabola that would form a collinear triple
with points to their left.

By concavity, any line intersects the curve $x/\log^{\varepsilon}$ in at most
two points. If we choose the squares in the construction to be small enough,
then (as we will see) a line intersects at most two of the squares.Thus to
avoid collinear triples, it is enough to delete a point from each line which
intersects the previously defined point set in one point and the parabola in
the $n$th square in two points, or vice versa. By bounding from above the
number of deleted points, we obtain $\Theta(\frac{N}{\log^{1+\varepsilon}N})$
lattice points in general position for each $[1,N]^{2}$, verifying Theorem
1.3.

####

In addition to the construction of Theorem 1.3, we also have some
computational results. The _lexicographic greedy construction_ on a subset $U$
of $\mathbb{N}^{2}$ proceeds from left to right across $U$. On each vertical
line, we add to $S$ the lowest point that is not on the same line with any two
already-placed points (if such a point exists). The lexicographic greedy
construction on the (infinite height) grid has been previously examined in
OEIS sequences A236335 and A236266 [14]. We consider the lexicographic greedy
construction over the triangular region consisting of the points with $y\leq
x$ in the first quadrant of $\mathbb{Z}^{2}$. In computer experiments, this
appears to stably yield slightly more than $0.8n$ points in general position
in $[1,n]^{2}$. We also consider the variant where we only take points on
vertical lines having even $x$-intercept. In computer experiments, this even
variant appears to find points without fail, yielding exactly $n$ points in
general position in $[1,2n]^{2}.$

The organisation of the paper is as follows. We finish this section by
presenting the outline of Theorem 1.3. In Section 2 we introduce the notation
we wish to use throughout the paper and recall some background results.
Section 3 is devoted to the proof of Theorem 1.3. Finally, in Section 4 we
describe computer experiments with the lexicographic greedy construction,
which suggest that the answer for Question 1.1 is “no”. Motivated by these
experiments, we formulate novel conjectures.

##  2 Preliminaries

######  Notation 2.1.

When speaking about the lattice points of a grid, $[1,N]$ denotes the integers
in the closed interval.

We will use (without further reference) the following well-known results from
analysis and number theory.

######  Result 2.2.

The first $N$ terms of the harmonic series sum up as
$\sum_{i=1}^{N}\frac{1}{k}=\ln N+O(1).$

######  Result 2.3 (Baker, Harman, Pintz [4]).

There is a prime number in the interval $[x-x^{21/40},x]$ for all large enough
$x$.

Let us recall the details of the parabola construction of Erdős discussed in
the introduction. This construction provides $n-o(n)$ points in general
position in the grid $[1,n]\times[1,n]$. We introduce a slightly generalized
form.

######  Construction 2.4 (The general modular parabola construction).

Let $\mathcal{P}$ denote a parabola $y=(x-a)^{2}+b\pmod{p}$ for some prime $p$
and integers $a,b$. The graph of the parabola in $[1,p]\times[1,p]$ lies in
general position, similarly to the Erdős construction. Indeed, the two extra
parameters $a,b$ merely translate the graph of $y=x^{2}\pmod{p}$.

We make two observations regarding Construction 2.4. The first states that two
points determine a unique parabola having leading coefficient $1$. The second
notices that that there is at most one point pair of the parabola with a given
direction and Euclidean distance.

######  Claim 2.5.

  1.   2. 1.

Let $\mathbb{F}$ be a field, and
$(x_{0},y_{0}),(x_{1},y_{1})\in\mathbb{F}\times\mathbb{F}.$ Then the system of
equations

$\left\\{\begin{array}[]{ll}(x_{0}-a)^{2}+b=y_{0}\\\
(x_{1}-a)^{2}+b=y_{1}\end{array}\right.$

has a unique solution $(a,b)$, provided that $x_{0}\neq x_{1}$.

  3. 2.

Let $\mathcal{P}$ be the parabola $y=(x-a)^{2}+b\pmod{p}$ on the grid
$[0,p-1]\times[0,p-1]\subseteq\mathbb{Z}^{2}$. Choose any ordered pair of
positive numbers $s,t$. There is at most one pair of points $Q_{1},Q_{2}$
lying on $\mathcal{P}$ for which the line segment $Q_{1}Q_{2}$ has slope $s$
and length $t$.

###### Proof.

To prove the first part, subtract the second equation from the first to get a
linear equation in $a$, which uniquely determines $a$. The uniqueness of $b$
now follows immediately.

To prove the second part, suppose that we have four points on the parabola,
$Q_{1},Q_{2},R_{1},R_{2},$ such that $R_{1}R_{2}$ is a translate of
$Q_{1}Q_{2}$. That is, the points have the form
$Q_{1}=(x_{0},y_{0}),Q_{2}=(x_{1},y_{1})$ and
$R_{1}=(x_{0}+u,y_{0}+v),R_{2}=(x_{1}+u,y_{1}+v)$. Then the following
equations hold:

$\begin{array}[]{ll}(x_{0}-a)^{2}+b=y_{0}\\\ (x_{1}-a)^{2}+b=y_{1}\\\
(x_{0}+u-a)^{2}+b=y_{0}+v\\\ (x_{1}+u-a)^{2}+b=y_{1}+v.\\\ \end{array}.$

However, the first two equations determine $(a,b)$ as in the proof of the
first part, and the last two equations determine the same pair $(a,b)$ if and
only if $u=v=0$. ∎

We will also frequently use the following bound throughout the proof of the
main theorem.

######  Claim 2.6.

Let $\varepsilon\in[0,1]$ be a non-negative real number. If $n>10$, then

$\sum_{m=1}^{n-1}\frac{2^{m}}{m^{1+\varepsilon}}\leq
2\cdot\frac{2^{n}}{n^{1+\varepsilon}}.$

###### Proof.

It is easy to see that the claim holds for $n=11$ for every $\varepsilon$,
since it in turn follows from the case $\varepsilon=1$ by monotonicity. To
prove for every $n>11$, one can easily apply induction. Then it is enough to
verify $\frac{2+1}{2\cdot 2}\leq(\frac{n}{n+1})^{1+\varepsilon}$ to prove the
inductional hypothesis. ∎

##  3 Proof of the main result

###  3.1 Construction

We begin by describing our construction.

The building blocks of the construction will be copies of the parabola of
Construction 2.4, taken over various primes $p$. We will place these copies
along the curve $x/\log^{\varepsilon}x$ (for some fixed small $\varepsilon$).
By concavity, no line passes through more than 2 points of this curve. If we
choose our parabolas to be small enough, then no line will pass through more
than two of the copies, and we can then control the lines passing through two
copies.

The details are as follows. It may be helpful to refer to Figure 1.

######  Construction 3.1 (Main construction).

Fix a real number $0<\varepsilon<1$. Fix also a real number $c$, which will be
at least $12/\varepsilon$ (see Lemma 3.2 below).

  1. 1.

For each sufficiently large $n$, consider an axis-parallel square $Q_{n}$ with
sides of length $\left\lfloor\frac{2^{n}}{cn^{1+\varepsilon}}\right\rfloor$,
and top left corner at
$(2^{n},\left\lfloor\frac{2^{n}}{n^{\varepsilon}}\right\rfloor)$. Let $p_{n}$
be the largest prime smaller than
$\left\lfloor\frac{2^{n}}{cn^{1+\varepsilon}}\right\rfloor$.

  2. 2.

In each $Q_{n}$, consider a translated copy of the parabola
$(x-a_{n})^{2}+b_{n}\mod p_{n}$ (for some choice of parameters $a_{n}$ and
$b_{n}$), extending down and right from the top left corner. Denote this
parabola as $\mathcal{P}_{n}$.

  3. 3.

Our point set $S$ will consist of a subset of $\bigcup_{n}\mathcal{P}_{n}$.

We will select the subset $S$ of $\bigcup\mathcal{P}_{n}$ iteratively.
Assuming that we have already selected points in
$\mathcal{P}_{1},\dots,\mathcal{P}_{n-1}$, we will select the parameters
$a_{n},b_{n}$ to minimize the number of collinear triples spanned by points of
$\mathcal{P}_{n}$ and $S\cap\left(\bigcup_{i=1}^{n-1}Q_{i}\right)$. We remove
one point of each such collinear triple from $\mathcal{P}_{n}$, and add the
remaining points to $S$.

The floors in the construction make no difference in the asymptotic situation,
and we will generally omit them to make our calculations easier to follow.

Figure 1: Illustration for Lemma 3.2

###  3.2 Bounding lemmas

Fix notation as in Construction 3.1. We first show that no line intersects
more than two copies of the modular parabola gadget.

######  Lemma 3.2.

If $c$ is at least $c_{0}(\varepsilon)$, then no line intersects more than two
of the squares $Q_{n}$.

###### Proof.

Suppose that $m<n<k$, and that $\ell$ is a line passing through the squares
$Q_{m}$ and $Q_{k}$. We desire to show that $Q_{n}$ lies strictly above
$\ell$.

Since the $x$ coordinates for $Q_{n}$ lie strictly between those for $Q_{m}$
and $Q_{k}$, and since the top edge of $Q_{m}$ lies strictly below that of
$Q_{k}$, we can assume without loss of generality that $\ell$ intersects
$Q_{m}$ and $Q_{k}$ at their top left corners. By concavity of the curve
$x/\log^{\varepsilon}x$, we may assume that $m=n-1$ and $k=n+1$.

We now want to show that the lower right hand corner of $Q_{n}$ is above
$\ell$. Since the slope of $\ell$ is clearly smaller than $1$, it suffices to
look at the left side of $Q_{n}$, and show that the difference between
$\left\lfloor\frac{2^{n}}{n^{\varepsilon}}\right\rfloor$ and the height here
of $\ell$ is at least
$2\cdot\left\lfloor\frac{2^{n}}{cn^{1+\varepsilon}}\right\rfloor$ (see Figure
1). Since $2^{n}/2^{n-1}$ and $2^{n+1}/2^{n}$ are in a $2:1$ ratio, this
difference is (ignoring floors)

$\frac{2^{n}}{n^{\varepsilon}}-\frac{2}{3}\cdot\frac{2^{n-1}}{(n-1)^{\varepsilon}}-\frac{1}{3}\cdot\frac{2^{n+1}}{(n+1)^{\varepsilon}}=\frac{2^{n}}{3n^{\varepsilon}}\cdot\left(3-\frac{n^{\varepsilon}}{(n-1)^{\varepsilon}}-\frac{2n^{\varepsilon}}{(n+1)^{\varepsilon}}\right),$

and so it is enough to choose $c$ so that

$3-\frac{n^{\varepsilon}}{(n-1)^{\varepsilon}}-\frac{2n^{\varepsilon}}{(n+1)^{\varepsilon}}=2\cdot\frac{(n+1)^{\varepsilon}-n^{\varepsilon}}{(n+1)^{\varepsilon}}-\frac{n^{\varepsilon}-(n-1)^{\varepsilon}}{(n-1)^{\varepsilon}}$

is at least $\frac{6}{cn}$. We recall a slight extension of Bernoulli’s
inequality, that $1+\varepsilon x>(1+x)^{\varepsilon}>1+\varepsilon
x+\varepsilon(\varepsilon-1)x^{2}/2$ when $0<\varepsilon<1$ and $-1<x<1$.
Here, the second inequality follows from alternating series estimation when
$x>0$, or from Taylor’s inequality when $x<0$. Thus, our chain of inequalities
continues:

$\displaystyle
2\cdot\frac{(n+1)^{\varepsilon}-n^{\varepsilon}}{(n+1)^{\varepsilon}}-\frac{n^{\varepsilon}-(n-1)^{\varepsilon}}{(n-1)^{\varepsilon}}$
$\displaystyle>2\cdot\frac{\varepsilon
n^{\varepsilon-1}+\varepsilon(\varepsilon-1)n^{\varepsilon-2}/2}{n^{\varepsilon}+\varepsilon
n^{\varepsilon-1}}-\frac{\varepsilon
n^{\varepsilon-1}+\varepsilon(\varepsilon-1)n^{\varepsilon-2}/2}{n^{\varepsilon}-\varepsilon
n^{\varepsilon-1}+\varepsilon(\varepsilon-1)n^{\varepsilon-2}}$
$\displaystyle=\frac{2\varepsilon}{n}\cdot\frac{1+\varepsilon
n^{-1}-n^{-1}/2}{1+\varepsilon
n^{-1}}-\frac{\varepsilon}{n}\cdot\frac{1+(\varepsilon-1)n^{-1}/2}{1-\varepsilon
n^{-1}+\varepsilon(\varepsilon-1)n^{-2}}$
$\displaystyle=\frac{\varepsilon}{n}\cdot\left(2-\frac{1}{n+\varepsilon}-\frac{1+(\varepsilon-1)n^{-1}/2}{1-\varepsilon
n^{-1}+\varepsilon(\varepsilon-1)n^{-2}}\right).$

As the last entry is greater than $\varepsilon/2n$ past very small $n$, we may
take $c_{0}$ to be $12/\varepsilon$. ∎

######  Lemma 3.3.

If $\ell$ is a line which intersects $Q_{m}$ and $Q_{n}$ for $m<n$ integers,
then the slope $\mu(\ell)$ satisfies

$\frac{2^{n-m}(\frac{1}{n^{\varepsilon}}-\frac{1}{cn^{1+\varepsilon}})-\frac{1}{m^{\varepsilon}}}{2^{n-m}(1+\frac{1}{cn^{1+\varepsilon}})-1}\leq\mu(\ell)\leq\frac{2^{n-m}/n^{\varepsilon}-\frac{1}{m^{\varepsilon}}+\frac{1}{cm^{1+\varepsilon}}}{2^{n-m}-1-\frac{1}{cm^{1+\varepsilon}}}.$

###### Proof.

Let $A_{i}$ and $D_{i}$ denote the top left and the bottom right corner of the
square $Q_{i}$, respectively, for $i\in\\{m,n\\}$. It is easy to see that the
smallest possible slope corresponds to the line $A_{m}D_{n}$ and the largest
possible slope corresponds to $D_{m}A_{n}$. Taking into consideration that
$A_{i}=(2^{i},\frac{2^{i}}{i^{\varepsilon}})$, and
$D_{i}=(2^{i}+\frac{2^{i}}{ci^{1+\varepsilon}},\frac{2^{i}}{i^{\varepsilon}}-\frac{2^{i}}{ci^{1+\varepsilon}})$,
we get the desired bounds. ∎

We will need the following technical result on the difference between the
upper and lower bounds of Lemma 3.3.

######  Lemma 3.4 (Technical Lemma).

Let $m<n$ be integers, and $0<\varepsilon<1$. If $n$ is sufficiently large,
then

$\frac{\frac{1}{n^{\varepsilon}}-\frac{1}{c2^{n-m}m^{\varepsilon}}+\frac{1}{c2^{n-m}m^{1+\varepsilon}}}{1-2^{n-m}-\frac{1}{c2^{n-m}m^{1+\varepsilon}}}-\frac{\frac{1}{n^{\varepsilon}}-\frac{1}{c2^{n-m}m^{\varepsilon}}-\frac{1}{cn^{1+\varepsilon}}}{1-2^{n-m}+\frac{1}{cn^{1+\varepsilon}}}<\frac{11}{cn^{1+\varepsilon}}.$

######  Corollary 3.5.

Let $\ell$ be a line having slope $\mu(\ell)=r/q$, and that intersects $Q_{m}$
and $Q_{n}$ for $m<n$ integers. If $n$ is sufficiently large, then $r$ can
admit at most $q\cdot\frac{11}{cn^{1+\varepsilon}}$ different values.

###### Proof (of Lemma 3.4).

The key step is to notice that as
$2^{n}/n^{1+\varepsilon}>2^{m}/m^{1+\varepsilon}$ for $n$ sufficiently large,
also $2^{n-m}m^{1+\varepsilon}>n^{1+\varepsilon}$. Write $A$ for
$\frac{1}{n^{\varepsilon}}-\frac{1}{c2^{n-m}m^{\varepsilon}}$ and $B$ for
$1-2^{n-m}$. Then the left-hand side of the inequality is

$\frac{A\cdot\left(\frac{1}{cn^{1+\varepsilon}}+\frac{1}{c2^{n-m}m^{1+\varepsilon}}\right)+\frac{1}{c2^{n-m}m^{1+\varepsilon}}\cdot\left(B+\frac{1}{cn^{1+\varepsilon}}\right)+\frac{1}{cn^{1+\varepsilon}}\cdot\left(B-\frac{1}{c2^{n-m}m^{1+\varepsilon}}\right)}{B^{2}(1\pm
o(1))}.$

Notice that $A\to 0$, as do the smaller terms on the bottom, and also that
$\frac{1}{2}<B<1$. Applying the key step, we thus bound the left-hand side for
large enough $n$ by

$\frac{\frac{1}{10}\cdot\frac{2}{cn^{1+\varepsilon}}+\frac{1}{cn^{1+\varepsilon}}\cdot\frac{11}{10}+\frac{1}{cn^{1+\varepsilon}}\cdot
1}{1/5}<\frac{11}{cn^{1+\varepsilon}}.\qed$

###  3.3 Red points and blue pairs

Lemma 3.2 says that any line passing through three points in our construction
must pass through two points in one square, and at least one point in another.
Lemma 3.3 and Corollary 3.5 will let us say that this is rare.

######  Lemma 3.6.

Let $m<n$, where $n$ is sufficiently large. The number of collinear triples
determined by two points from $S\cap Q_{m}$ and one lattice point of $Q_{n}$
is at most

$\frac{8\cdot 2^{m+n}}{c^{3}n^{2+2\varepsilon}m^{1+\varepsilon}}\cdot n.$

###### Proof.

We first count the number of lines $\ell$ intersecting $S\cap Q_{m}$ in two
points according to the denominator of their slope. Let $\ell$ have slope
$\mu(\ell)=\frac{r}{q}$, where $r$ and $q$ are relatively prime. Consider the
projection onto the $x$ axis of the line segment between the two points of
intersection. The length $d$ of this projection must be a multiple of $q$, at
most $\frac{2^{m}}{c\cdot m^{1+\varepsilon}}$. Moreover, it follows from Claim
2.5 that $d$ and $\frac{r}{q}$ uniquely determine the two points on $S\cap
Q_{m}$, so each value of $d$ occurs at most once.

Thus, we have at most $\frac{2^{m}}{q\cdot c\cdot m^{1+\varepsilon}}$ pairs
from $S\cap Q_{m}$ determining a line of slope $r/q$. If $\ell$ also passes
through $Q_{n}$, then by Corollary 3.5 there are at most
$q\cdot\frac{11}{cn^{1+\varepsilon}}$ possible values of $r$. By examining the
$x$ coordinate, there are at most $\frac{2^{n}}{q\cdot c\cdot
n^{1+\varepsilon}}$ lattice points in $Q_{n}$ lying on $\ell$.

We finish the proof by summing over possible values of $q$, noticing that
$11\cdot\ln 2<8$ and taking into consideration Result 2.2:

$\displaystyle\sum_{q<\frac{2^{m}}{cm^{1+\varepsilon}}}\frac{1}{q}\cdot\frac{2^{n}}{cn^{1+\varepsilon}}\cdot\frac{2^{m}}{cm^{1+\varepsilon}}\cdot\frac{11}{cn^{1+\varepsilon}}$
$\displaystyle\leq\frac{11\cdot
2^{m+n}}{c^{3}n^{2+2\varepsilon}m^{1+\varepsilon}}\cdot(\ln(\frac{2^{m}}{cm^{1+\varepsilon}})+O(1))$
$\displaystyle<\frac{8\cdot
2^{m+n}}{c^{3}n^{2+2\varepsilon}m^{1+\varepsilon}}\cdot n.\qed$

We color as red the points in $Q_{n}$ that are on the same line with a pair of
points in $S\cap Q_{m}$ for some $m<n$. By summing the bound of Lemma 3.6 over
all $m<n$ and applying Claim 2.6, we see that:

######  Corollary 3.7.

The number of red points in $Q_{n}$ is at most

$\sum_{m<n}\frac{8\cdot
2^{m+n}}{c^{3}n^{2+2\varepsilon}m^{1+\varepsilon}}\cdot n<\frac{16\cdot
2^{n+n}}{c^{3}n^{2+2\varepsilon}n^{1+\varepsilon}}\cdot n.$ (1)

We notice that the ratio between the number of red points and the number of
all points of $Q_{n}$ is at most $\frac{16}{cn^{\varepsilon}}$. Thus, it is
clear that we will be able to choose $a_{n},b_{n}$ as in Construction 3.1 to
avoid all but an insignificant number of red points.

However, we must now also consider lines that intersect two points in $Q_{n}$,
together with some point in $S\cap Q_{m}$ for some $m<n$. In analogy with our
red points, we call a pair of lattice points in $Q_{n}$ _blue_ if at least one
of the pair is not red, and if the two are on a common line with a point of
$S\cap Q_{m}$ for some $m<n$. Thus, to prove Theorem 1.3, it will suffice to
show that there is a choice of $a_{n},b_{n}$ that simultaneously avoids all
but a small number of both red points and blue pairs.

######  Lemma 3.8.

The number of blue pairs in $Q_{n}$ is at most $\ \displaystyle{\frac{8\cdot
2^{3n}}{c^{4}n^{3+4\varepsilon}}}.$

###### Proof.

Consider a fixed $m<n$, and fix the denominator $q$ of the slope $r/q$ of a
line $\ell$ that intersects $S\cap Q_{m}$ and at least one blue pair of
$Q_{n}$. As in the proof of Lemma 3.6, Corollary 3.5 gives that there are at
most $q\cdot\frac{11}{cn^{1+\varepsilon}}$ choices for $r$.

If $\ell$ would pass through more than one point of $Q_{m}$, then all points
on $\ell$ in $Q_{n}$ would be colored red, and in particular none of them
would be in a blue pair. Thus, the line $\ell$ is determined (given $r$) by
its intersection with $S\cap Q_{m}$, and we have at most $|S\cap
Q_{m}|\leq\frac{2^{m}}{cm^{1+\varepsilon}}$ such lines. Finally, on each line
we have at most

${\binom{\frac{2^{n}}{q\cdot
cn^{1+\varepsilon}}}{2}}<\frac{2^{2n}}{2q^{2}c^{2}n^{2+2\varepsilon}}$

points from $Q_{n}$. Combining these choices, we have at most

$\frac{1}{q}\cdot\frac{11}{cn^{1+\varepsilon}}\cdot\frac{2^{m}}{cm^{1+\varepsilon}}\cdot\frac{2^{2n}}{2c^{2}n^{2+2\varepsilon}}$

pairs relative to a fixed $q$ and $m$. We now notice that as $\ell$ passes
through two points of $Q_{n}$, we must have
$q<\frac{2^{n}}{cn^{1+\varepsilon}}$. Summing over $q$ and $m$, in view of
Result 2.2 and Claim 2.6, we obtain

$\sum_{m=1}^{n-1}\sum_{q<\frac{2^{n}}{cn^{1+\varepsilon}}}\frac{1}{q}\cdot\frac{2^{m}}{cm^{1+\varepsilon}}\cdot\frac{11\cdot
2^{2n}}{2c^{3}n^{3+3\varepsilon}}\leq\sum_{m}\frac{2^{m}}{cm^{1+\varepsilon}}\cdot\frac{8\cdot
2^{2n}}{2c^{3}n^{3+3\varepsilon}}\cdot n\leq\frac{8\cdot
2^{3n}}{c^{4}n^{3+4\varepsilon}}.\qed$

###  3.4 Proof of Theorem 1.3

We build our point set as in Construction 3.1, using a value of $c$ large
enough to satisfy the condition of Lemma 3.2. It follows from Claim 2.6 that
$\sum p_{n}$ has the desired growth rate. Thus, provided the number of deleted
points from each $Q_{n}$ is small, our iteratively-defined set $S$ will
satisfy the requirement of the theorem. We will show that for every
$n\in\mathbb{N}$, there is a choice of parameters $a_{n},b_{n}$, so that the
number of points deleted from each $Q_{n}$ is of the order
$p_{n}/n^{\varepsilon}$.

Lemma 3.2 implies that, due to the sizes and positions of the squares $Q_{n}$,
there will be no collinear triples formed by points of three distinct squares
$Q_{i}$. Certain points (the red points of Section 3.3) or pairs of points
(the blue pairs of the same section) from $Q_{n}$ may form a collinear triple
with a point or points of $S\cap Q_{m}$ for some $m<n$.

We will show that the number of such collinear triples is small. We will use a
double counting argument on the set $\mathcal{I}$ of pairs $(\mathcal{P},T)$,
where $\mathcal{P}$ is a parabola modulo $p_{n}$ in $Q_{n}$, and $T$ is a
collinear triple on $\mathcal{P}\cup(S\cap Q_{m})$ for some $m<n$.

We first count $\mathcal{I}$ by collinear triples. Each red point of $Q_{n}$
determines a collinear triple with two points from $S\cap Q_{m}$ (some $m<n)$,
and lies on exactly $p_{n}$ parabolas. Each blue pair of $Q_{n}$ determines a
collinear triple with some point from $S\cap Q_{m}$ (some $m<n$), and lies on
a unique parabola. It follows that

$\displaystyle\left|\mathcal{I}\right|$
$\displaystyle=\left|\\{(\mathcal{P},C):C\in\mathcal{P}\mbox{ is
red}\\}\right|+\left|\\{(\mathcal{P},\\{C,D\\}):\\{C,D\\}\subseteq\mathcal{P}\text{
is a blue pair}\\}\right|$ $\displaystyle\leq\frac{16\cdot
2^{2n}}{c^{3}n^{2+3\varepsilon}}\cdot p_{n}+\frac{8\cdot
2^{3n}}{c^{4}n^{3+4\varepsilon}}.$

We now count $\mathcal{I}$ by parabolas. Indeed, as there are $p_{n}$ choices
for each of $a$ and $b$, the mean number of pairs $(\mathcal{P}(a,b),T)$ in
$\mathcal{I}$ for a choice of parameters $(a,b)$ is
$\left|\mathcal{I}\right|/p_{n}^{2}$. In particular, there is some choice
$a_{n},b_{n}$ of parameters for a parabola in $Q_{n}$ with at most

$\left(\frac{16\cdot 2^{2n}}{c^{3}n^{2+3\varepsilon}}\cdot p_{n}+\frac{8\cdot
2^{3n}}{c^{4}n^{3+4\varepsilon}}\right)\bigg{/}p_{n}^{2}=O\left(\frac{2^{n}}{n^{1+2\varepsilon}}\right)$

pairs in $\mathcal{I}$ having $\mathcal{P}_{n}:=\mathcal{P}(a_{n},b_{n})$ in
the parabola entry.

We now form $S\cap Q_{n}$ by selecting the parabola $\mathcal{P}_{n}$, and
deleting a point from each collinear triple $T$ so that $(\mathcal{P}_{n},T)$
is in $\mathcal{I}$. Thus, we delete from $\mathcal{P}_{n}$ all incident red
points, and one point from each incident blue pair. As $p_{n}$ is only
slightly smaller than $\frac{2^{n}}{cn^{1+\varepsilon}}$, the number of points
in the constructed $S\cap Q_{n}$ is
$\frac{2^{n}}{cn^{1+\varepsilon}}\cdot(1-o(n))$. This suffices to complete the
proof.

##  4 Greedy lexicographic construction

Figure 2: Construction $S_{\mathrm{lex}<}$ for $n=500$

A concrete and deterministic construction for large grid sets that are in
general position may be described as follows. We iteratively look at each
vertical line $x=1$, $x=2$, etc. At each line $x=i$, we record the least
positive $j$ so that the point $(i,j)$ is not on a common line with any two
points to its left. The limit of this process yields an infinite set
$S_{\mathrm{lex}}$ of triple-wise non-collinear integer points. This
construction has been previously examined in OEIS sequence A236335, and
similar constructions are the subject of sequences A236266, A179040 [21].

Since we are interested in high density in squares $[1,n]^{2}$, we vary the
lexicographic construction slightly to require $j<i$ at each step, yielding a
set $S_{\mathrm{lex}<}$. Experimental evidence suggests that $[1,n]^{2}\cap
S_{\mathrm{lex}<}$ is of approximate size that is slightly larger than
$0.8\cdot n$. Refer to Table 1 for densities of $S_{\mathrm{lex}<}$ at several
values of $n$, or to Figure 2 for a plot of the first points in
$S_{\mathrm{lex}<}$.

$n$ | 100 | 200 | 300 | 400 | 500 | 1000 | 2000 | 3000 | 4000 | 5000 | 10000
---|---|---|---|---|---|---|---|---|---|---|---
# points $S_{\mathrm{lex}<}$ | $81$ | $166$ | $254$ | $340$ | $424$ | $830$ | $1678$ | $2515$ | $3353$ | $4197$ | $8385$
density % $n$ | $81\%$ | $83$ | $84.6$ | $85$ | $84.8$ | $83$ | $83.9$ | $83.8$ | $83.8$ | $83.9$ | $83.9$
# points $S_{\mathrm{mod2lex}}$ | $50$ | $100$ | $150$ | $200$ | $250$ | $500$ | $1000$ | $1500$ | $2000$ | $2500$ | $5000$
density % $n$ | $50\%$ | $50$ | $50$ | $50$ | $50$ | $50$ | $50$ | $50$ | $50$ | $50$ | $50$
Table 1: Density achieved by the lexicographic greedy construction

A variant of some interest is to look only at the even lines $x=2$, $x=4$,
etc., and to apply the lexicographic construction on these, again with the
requirement that $j<i$ at each step. We call the obtained set
$S_{\mathrm{mod2lex}}$. Experimental evidence suggests that the lexicographic
construction always yields a general position point above each even $i$;
moreover, in our experiments, this point always lies so that $j<\frac{2}{3}i$
(see Figure 3). Rigorous analysis of this type of greedy approach appears to
be difficult.

Figure 3: Construction $S_{\mathrm{mod2lex}<}$ for $n=800$

######  Conjecture 4.1.

$S_{\mathrm{lex<}}$ and $S_{\mathrm{mod2lex<}}$ provide a point set such that
the number of points in each square $[1,n]\times[1,n]$ can be bounded from
below by a linear function.

The consistent behavior of $S_{\mathrm{mod2lex<}}$ suggests that it might be
more amenable to rigorous analysis than other greedy constructions.

#### Acknowledgement.

The paper resulted from the 11th Emléktábla Workshop, where Dömötör Pálvölgyi
made us aware of the problem. We are grateful to the organisers of the
workshop. We also thank Joshua Erde for first proposing the problem.

## References

  * [1] Michael A. Adena, Derek A. Holton, and Patrick A. Kelly, _Some thoughts on the no-three-in-line problem_ , Combinatorial mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973), 1974, pp. 6–17. Lecture Notes in Math., Vol. 403.
  * [2] Oswin Aichholzer, David Eppstein, and Eva-Maria Hainzl, _Geometric dominating sets - a minimum version of the No-Three-In-Line problem_ , Computational Geometry 108 (2023), Article 101913.
  * [3] David Brent Anderson, _Update on the no-three-in-line problem_ , Journal of Combinatorial Theory, Series A 27 (1979), no. 3, 365–366.
  * [4] R. C. Baker, G. Harman, and J. Pintz, _The difference between consecutive primes. II_ , Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562.
  * [5] Simeon Ball and James William Peter Hirschfeld, _Bounds on (n, r)-arcs and their application to linear codes_ , Finite Fields and Their Applications 11 (2005), no. 3, 326–336.
  * [6] Simeon Ball and Michel Lavrauw, _Arcs in finite projective spaces_ , EMS Surveys in Mathematical Sciences 6 (2020), no. 1, 133–172.
  * [7] Raj Chandra Bose, _Mathematical theory of the symmetrical factorial design_ , Sankhyā: The Indian Journal of Statistics (1947), 107–166.
  * [8] Peter Brass, William O. J. Moser, and János Pach, _Lattice point problems_ , pp. 417–433, Springer New York, New York, NY, 2005.
  * [9] Henry E Dudeney, _Amusements in mathematics_ , vol. 473, Courier Corporation, 1917.
  * [10] David Eppstein, _Forbidden configurations in discrete geometry_ , Cambridge University Press, 2018.
  * [11] Achim Flammenkamp, _Progress in the no-three-in-line problem, ii_ , Journal of Combinatorial Theory, Series A 81 (1998), no. 1, 108–113.
  * [12] Martin Gardner, _Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer_ , Scientific American 235 (1976), no. 4, 131–137.
  * [13] R. R. Hall, T. H. Jackson, A. Sudbery, and K. Wild, _Some advances in the no-three-in-line problem_ , J. Combinatorial Theory Ser. A 18 (1975), 336–341. MR 366817
  * [14] OEIS Foundation Inc., _The On-line Encyclopedia of Integer Sequences_ , Published electronically at https://oeis.org/, 2022.
  * [15] J.H. Kim and V.H. Vu, _Small complete arcs in projective planes_ , Combinatorica 2 (2003), no. 23, 311–363.
  * [16] Michael S. Payne and David R. Wood, _On the general position subset selection problem_ , SIAM J. Discrete Math. 27 (2013), no. 4, 1727–1733.
  * [17] Attila Pór and David R Wood, _No-three-in-line-in-3D_ , Algorithmica 47 (2007), no. 4, 481–488.
  * [18] Karl F. Roth, _On a problem of Heilbronn_ , J. London Math. Soc. 26 (1951), 198–204. MR 41889
  * [19] Beniamino Segre, _Curve razionali normali e $k$-archi negli spazi finiti_, Ann. Mat. Pura Appl. (4) 39 (1955), 357–379.
  * [20] , _Ovals in a finite projective plane_ , Canadian J. Math. 7 (1955), 414–416.
  * [21] Neil J.A. Sloane, _The on-line encyclopedia of integer sequences_ , Towards mechanized mathematical assistants, Springer, 2007, pp. 130–130.
  * [22] David R. Wood, _Grid drawings of $k$-colourable graphs_, Comput. Geom. 30 (2005), no. 1, 25–28.


#2 900 5mu -

áá1 éé1 íí1 óó1 úú1
ÁÁ1 ÉÉ1 ÍÍ1 ÓÓ1 ÚÚ1
àà1 èè1 ìì1 òò1 ùù1
ÀÀ1 ÈÉ1 ÌÌ1 ÒÒ1 ÙÙ1
ää1 ëë1 ïï1 öö1 üü1
ÄÄ1 ËË1 ÏÏ1 ÖÖ1 ÜÜ1
ââ1 êê1 îî1 ôô1 ûû1
ÂÂ1 ÊÊ1 ÎÎ1 ÔÔ1 ÛÛ1
œœ1 ŒŒ1 ææ1 ÆÆ1 ßß1
çç1 ÇÇ1 øø1 åå1 ÅÅ1
€1 £1

áá1 éé1 íí1 óó1 úú1
ÁÁ1 ÉÉ1 ÍÍ1 ÓÓ1 ÚÚ1
àà1 èè1 ìì1 òò1 ùù1
ÀÀ1 ÈÉ1 ÌÌ1 ÒÒ1 ÙÙ1
ää1 ëë1 ïï1 öö1 üü1
ÄÄ1 ËË1 ÏÏ1 ÖÖ1 ÜÜ1
ââ1 êê1 îî1 ôô1 ûû1
ÂÂ1 ÊÊ1 ÎÎ1 ÔÔ1 ÛÛ1
œœ1 ŒŒ1 ææ1 ÆÆ1 ßß1
çç1 ÇÇ1 øø1 åå1 ÅÅ1
€1 £1,

áá1 éé1 íí1 óó1 úú1
ÁÁ1 ÉÉ1 ÍÍ1 ÓÓ1 ÚÚ1
àà1 èè1 ìì1 òò1 ùù1
ÀÀ1 ÈÉ1 ÌÌ1 ÒÒ1 ÙÙ1
ää1 ëë1 ïï1 öö1 üü1
ÄÄ1 ËË1 ÏÏ1 ÖÖ1 ÜÜ1
ââ1 êê1 îî1 ôô1 ûû1
ÂÂ1 ÊÊ1 ÎÎ1 ÔÔ1 ÛÛ1
œœ1 ŒŒ1 ææ1 ÆÆ1 ßß1
çç1 ÇÇ1 øø1 åå1 ÅÅ1
€1 £1,

colframe = #2!25,
colback  = #2!12,
coltitle = #2!8!black,
title    = #3,

colframe = green!5!white,
colback  = green!75!black,
colbacktitle = green!85!black,
title    = #2,

[scale=0.4](0,.35) – (.25,0) – (1,.7) – (.25,.15) – cycle;

What Kinds of Contracts Do ML APIs Need?

Samantha Syeda Khairunnesa  Shibbir Ahmed  Sayem Mohammad Imtiaz Hridesh Rajan Gary T. Leavens

Samantha Syeda Khairunnesa  Dept. of Computer Science and Information Systems, Bradley University

Shibbir Ahmed  Dept. of Computer Science, Iowa State University

Sayem Mohammad Imtiaz  Dept. of Computer Science, Iowa State University

Hridesh Rajan  Dept. of Computer Science, Iowa State University

Gary T. Leavens  Dept. of Computer Science, University of Central Florida

Recent work has shown that Machine Learning () programs are error-prone and called for contracts for  code. Contracts, as in the design by contract methodology, help document APIs and aid API users in writing correct code.

The question is: what kinds of contracts would provide the most help to API users?
We are especially interested in what kinds of contracts help API users
catch errors at earlier stages in the  pipeline.
We describe an empirical study of posts on
Stack Overflow
of the four most often-discussed  libraries:
, , , and .
For these libraries, our study extracted 413 informal (English) API specifications.
We used these specifications to understand the following questions.
What are the root causes and effects behind contract violations?
Are there common patterns of contract violations?

When does understanding contracts require an advanced level of software expertise?
Could checking contracts at the API level help detect the violations in early  pipeline stages?
Our key findings are that the most commonly needed contracts for  APIs are either checking constraints on single arguments of an API or
on the order of API calls.
The software engineering community could employ existing contract mining approaches to mine
these contracts to promote an increased understanding of  APIs.
We also noted a need to combine
behavioral and temporal contract mining approaches.
We report on categories of required  contracts, which may help designers of contract languages.

Recent work has shown that Machine Learning () programs are error-prone and called for contracts for  code. Contracts, as in the design by contract methodology, help document APIs and aid API users in writing correct code.

The question is: what kinds of contracts would provide the most help to API users?
We are especially interested in what kinds of contracts help API users
catch errors at earlier stages in the  pipeline.
We describe an empirical study of posts on
Stack Overflow
of the four most often-discussed  libraries:
, , , and .
For these libraries, our study extracted 413 informal (English) API specifications.
We used these specifications to understand the following questions.
What are the root causes and effects behind contract violations?
Are there common patterns of contract violations?

When does understanding contracts require an advanced level of software expertise?
Could checking contracts at the API level help detect the violations in early  pipeline stages?
Our key findings are that the most commonly needed contracts for  APIs are either checking constraints on single arguments of an API or
on the order of API calls.
The software engineering community could employ existing contract mining approaches to mine
these contracts to promote an increased understanding of  APIs.
We also noted a need to combine
behavioral and temporal contract mining approaches.
We report on categories of required  contracts, which may help designers of contract languages.

This material is based upon work supported by the National Science Foundation under Grant CCF-15-18897, CNS-15-13263, CCF-17-23215, CCF-17-23432, CCF-19-34884, CNS-17-23198, CCF-22-23812. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

§ DATA AVAILABILITY STATEMENT

The dataset (labeled posts, queries, source codes, etc.) generated during the study are available in the figshare repository, <https://figshare.com/s/c288c02598a417a434df>.

§ CONFLICT OF INTEREST

The authors declare conflict of interest with the people affiliated with Iowa State University, University of Central Florida, and Bradley University.


# Deep neural network Models trained with a fixed Random classifier transfer
better across domains

###### Abstract

The recently discovered Neural collapse (NC) phenomenon states that the last-
layer weights of Deep Neural Networks (DNN), converge to the so-called
_Equiangular Tight Frame (ETF)_ simplex, at the terminal phase of their
training. This ETF geometry is equivalent to vanishing within-class
variability of the last layer activations. Inspired by NC properties, we
explore in this paper the transferability of DNN models trained with their
last layer weight fixed according to ETF. This enforces class separation by
eliminating class covariance information, effectively providing implicit
regularization. We show that DNN models trained with such a fixed classifier
significantly improve transfer performance, particularly on out-of-domain
datasets. On a broad range of fine-grained image classification datasets, our
approach outperforms $i)$ baseline methods that do not perform any covariance
regularization (up to $22\%$), as well as $ii)$ methods that explicitly whiten
covariance of activations throughout training (up to $19\%$). Our findings
suggest that DNNs trained with fixed ETF classifiers offer a powerful
mechanism for improving transfer learning across domains.

Index Terms—  Transfer learning, Neural Collapse, Random Projections, Deep
Learning Models.

##  1 Introduction

Deep neural networks (DNNs) have revolutionized machine learning and pattern
recognition tasks by providing highly expressive feature extractors. Recent
trends in training DNN models involve the use of fixed classifiers[1, 2, 3]
instead of traditional trainable linear layers on top of features extracted
from the last layer of the DNNs. This approach is inspired by the Neural
Collapse (NC) phenomenon [4, 5], which occurs during the late stages of model
training. NC reveals that features obtained from the last layer of the network
converge to class means with their within-class variability collapsing to zero
and forming the so-called Equiangular Tight Frame (ETF) geometry; the last-
layer linear classifiers are perfectly matched with their class activation
means, resulting in classifiers with ETF geometry.

Fig. 1: DNN models pretrained on a source domain $S$ with a classifier
following the ETF geometry implicitly minimize class features variability.
This translates into increased transferability to out-of-distribution target
domains $T$.

In this paper, we explore the transferability of training DNN models with
fixed classifiers following an ETF geometry. The ETF structure implicitly
enforces negligible within-class variability of features, thus enhancing
cluster separability which in turn, significantly improves transfer
performance. Our experiments focus on evaluating these models on various fine-
grained image classification datasets, and especially on out-of-domain
scenarios. Our contributions can be summarized as follows:

  1. 1.

Through the use of existing results in Random Matrix Theory (RMT), we
establish that the utilization of a linear random projector adheres to ETF
classifiers properties, leading to a feature kernel with minimal class
covariance.

  2. 2.

We then empirically show that DNNs trained with fixed ETF classifiers lead to
enhanced transfer performance on a range of fine-grained image classification
datasets, especially on those with important domain shifts with respect to the
source dataset (see Figure 1).

  3. 3.

We compare and show superior performance of our approach with baseline methods
that train the linear classifier from scratch (_no covariance minimization_),
as well as methods such as SW (Switchable Whitening) [6], that explicitly
perform features covariance whitening during training.

Notations. Vectors (matrices) are denoted by lowercase (uppercase) boldface
letters. $\left\\{{\bf v}_{a}\right\\}_{a=1}^{n}$ is the column vector ${\bf
v}$ with (scalar or vector) entries ${\bf v}_{a}$ and $\left\\{{\bf
V}_{ab}\right\\}_{a,b=1}^{n}$ is the matrix ${\bf V}$ with (scalar or matrix)
entries ${\bf V}_{ab}$. The vector ${\bf 1}\in\mathbb{R}^{n}$ stands for the
column vector filled with ones. The vector ${\bf j}_{a}$ is the canonical
vector of class $\mathcal{C}_{a}$ defined by $({\bf j}_{a})_{i}=\delta_{{\bf
x}_{i}\in\mathcal{C}_{a}}$ and ${\bf J}=[{\bf j}_{1},\ldots,{\bf
j}_{K}]\in\\{0,1\\}^{N\times K}$.

##  2 Related work

The NC phenomenon, as illuminated by recent research [4, 7, 8], sheds light on
the evolving behavior of features in DNN models during the late stages of
training. It posits that more expressive models possess the capability to
selectively discard class-covariance. Building upon the insights from NC,
recent contributions [2, 3] have harnessed the properties of NC by utilizing
fixed random classifiers to train backbone models. These models are designed
to generate features that align with the geometric structure of the fixed
random classifier. Notably, these studies have demonstrated improved
performance, particularly when dealing with training data exhibiting inherent
class imbalance. In this paper, we go further by showcasing that models
equipped with this mechanism also exhibit significant enhanced
transferability, especially when faced with out-of-distribution target data.
This remarkable improvement in transferability can be attributed to the
trivial separation of features per class, achieved by eliminating class
covariances during training.

In contrast to numerous methods that explicitly whiten features covariances
(enforce covariance matrix to be close to the identity matrix) during training
using dedicated loss functions [6], our approach focuses on enforcing
negligeable within-class variability, throughout training. Whitening
operations discard the variability between all features within a batch, while
the use of fixed ETF classifier adhere to the properties of NC by implicitly
discarding _within-class features variability_.

Our work bridges the application of fixed ETF classifiers with the use of
Random Projection (RP) classifiers. Random Matrix Theory has proven invaluable
for analyzing the behavior of various machine learning methods, in particular
RP [9]. In a related study [10], kernels obtained from random projectors with
generic activation functions were analyzed. However, this study operates under
the Gaussian Mixture Model (GMM) assumption, aiming to achieve "non-trivial"
separation based on class means and class covariances. We establish that the
utilization of a linear random projector adheres to ETF classifiers
properties, leading to a feature kernel with minimal class covariance. This
observation rationalizes the use of fixed random classifiers adhering to the
ETF geometry, which can essentially be seen as a random projector with a
linear activation function.

In summary, our study extends the potential of fixed ETF classifiers by
showcasing their effectiveness in cross-domain transfer tasks. This research
offers a perspective of the role played by fixed ETF classifiers in feature
transformation and transfer learning, particularly when confronted with
diverse data distributions.

##  3 Transfer Learning with Fixed ETF Classifiers

###  3.1 Linear random features exhibit minimal class covariance and thus
achieve NC

In this section, we aim to establish the equivalence between the Neural
Collapse (NC) phenomenon and the use of linear random features for enhancing
classification robustness and generalization. Our goal is to elucidate the
design of a random projector that transforms features learned by DNN models
into a space where they are linearly separable.

To this end, we consider a classification task with $K$ classes
$\\{\mathcal{C}_{k}\\}_{k=1}^{K}$, where $n$ training features $\\{{\bf
x}_{i}\in\mathbb{R}^{p}\\}_{i=1}^{n}$ belong to one of the $K$ classes. Our
objective is to demonstrate the design of a random projector that transforms
these features into a space where they are linearly separable. These features
are extracted from a pretrained DNN model, allowing us to model them using a
Gaussian Mixture Model (GMM) as shown in previous works [11]. This means that
$\\{{\bf x}_{i}\\}_{i=1}^{n}$ are independent vectors belonging to
$\\{\mathcal{C}_{k}\\}_{k=1}^{K}$, such that ${\bf x}_{i}\in\mathcal{C}_{a}$
can be modeled as

${\bf x}_{i}={\bm{\mu}}_{a}+{\bf C}_{a}^{\frac{1}{2}}{\bf z}_{i}$

where ${\bf z}_{i}\in\mathbb{R}^{p}$ is uniformly distributed at random on the
$\sqrt{p}$-radius sphere $\mathcal{S}^{p-1}$ of $\mathbb{R}^{p}$, and
${\bm{\mu}}_{a}\in\mathbb{R}^{p}$, ${\bf C}_{a}\in\mathbb{R}^{p\times p}$ are
the deterministic class means and class covariances of ${\bf x}_{i}$.

The Neural Collapse (NC) phenomenon [4] occurs when several conditions are met
for features extracted using a DNN model $f$. These conditions are: $i)$ The
within-class variability of features obtained before the last layer of $f$
converges to zero. $ii)$ The features extracted from samples of each class
converge to their class means, forming an ETF. $iii)$ The normalized weight
vector corresponding to each class features extracted at the last linear layer
of $f$ converges to the corresponding class mean of the features. Now, let
${\bf X}=[{\bf x}_{i}]_{i=1}^{n}\in\mathbb{R}^{p\times n}$, ${\bf
M}=[{\bm{\mu}}_{i}]_{i=1}^{K}\in\mathbb{R}^{p\times K}$, and ${\bf
C}^{\circ}=\sum_{a=1}^{K}\frac{n_{a}}{n}{\bf C}_{a}$. We can associate the NC
properties as follows:

  1. 1.

Property $i)$ is equivalent to ${\bf C}^{\circ}\to{\bf 0}$.

  2. 2.

Property $ii)$ is equivalent to ${\bf X}^{T}{\bf X}\to{\bf M}^{T}{\bf M}$.

  3. 3.

Property $iii)$ states that the weight matrix of the classifier is ${\bf
W}=\sqrt{\frac{K}{K-1}}{\bf PQ}$ where ${\bf P}={\bf I}_{K}-\frac{1}{K}{\bf
1}_{K}{\bf 1}_{K}^{T}$ and ${\bf Q}\in\mathbb{R}^{K\times p}$ is a random
orthogonal matrix.

A linear classifier with the weights ${\bf W}$ is called a fixed ETF
classifier.

Our objective is to establish the equivalence between the properties of NC and
the use of linear random features. To this end, we define random features by
$\sigma({\bf WX})$ with ${\bf W}$ and ${\bf X}$ defined earlier, and
$\sigma(\cdot)$ a generic activation function. Our goal is to prove that a
linear activation $\sigma(t)=t$ achieves NC.

We make use of existing RMT results in this context. While various RMT
algorithms [12, 13, 14] have been developed to discriminate both class means
and class covariances of features ${\bf x}_{i}$, it turns out that for the
final stages of training, discriminating only the class means is sufficient to
improve robustness and generalization of classifiers.

Since the properties of NC are summarized in terms of features covariance, we
define the kernel (random feature covariance) by ${\bf
K}=\frac{1}{p}\mathbb{E}_{{\bf W}}\sigma({\bf WX})^{T}\sigma({\bf WX}),$ where
the expectation is over the set of orthogonal random matrices. Under specific
growth rates (with respect to the dimension of features) assumptions on class
mean and class covariance functionals, [10] provides a random equivalent of
${\bf K}$ as a function of class means and covariances, for a broad class of
activation functions that satisfy boundedness of their first and second
derivatives. Theorem $1$ in [10] states that the kernel corresponding to
random features can be decomposed into two terms:

  1. 1.

$d_{1}{\bf X}^{T}{\bf X}=d_{1}\cdot\left({\bf Z}+{\bf M}\frac{{\bf J}^{\sf
T}}{\sqrt{p}}\right)^{\sf T}\left({\bf Z}+{\bf M}\frac{{\bf J}^{\sf
T}}{\sqrt{p}}\right)$ which is essentially the kernel of the features when no
random projection is applied. This means that the kernel term $d_{1}{\bf
X}^{T}{\bf X}$ retains the inherent structure of the features ${\bf X}$.

  2. 2.

$d_{2}\cdot\left({\bm{\phi}}+{\bf VAV}^{\sf T}\right)$ only containing
information about the class covariances (${\rm tr}{\bf C}_{a}^{\circ},{\rm
tr}{\bf C}_{a}^{\circ}{\bf C}_{b}^{\circ}$). This means that the kernel term
responsible for class covariances vanishes.

According to Property $i)$ of NC, ${\bf C}_{a}^{\circ}\to 0$ (as ${\bf
C}^{\circ}=\sum_{a=1}^{K}\frac{n_{a}}{n}{\bf C}_{a}\to{\bf 0}$). Consequently,
we want $d_{2}=0$ to achieve Property $i).$ Regarding Property $2,$ as long as
the features are extracted from a stronger feature extractor, $d_{1}{\bf
X}^{T}{\bf X}$ will be closer to ${\bf M}^{T}{\bf M}$. In other words, a
stronger feature extractor will have a lower energy for the matrix ${\bf Z}$
compared to the signal matrix ${\bf M}$. For a linear activation function
$\sigma(t)=t,$ $d_{1}=1$ and $d_{2}=0$ implying that training a strong feature
extractor along with a fixed linear random projector, results in maximal class
separation. Note that ${\bf Z}$ contains random Gaussian columns with zero
mean and covariance ${\bf C}_{a}$. The use of a linear random classifier to
train the feature extractor forces ${\bf C}_{a}$ to be negligible.

$-1$$0$$1$$0.4$$0.6$$0.8$$1$$1.2$$a_{2}$MSE Fig. 2:  Test MSE. Random feature
regression with activation function $\sigma(t)=a_{2}t^{2}+t$. Features
extracted from the STL dataset using RN50 model pretrained on Imagenet.  Fig.
3: Heatmap of the covariance matrices ${\bf C}^{\circ}$ of features obtained
after transfer learning on the Flowers dataset using the RN101 model
pretrained on the ImageNet dataset. $a)$ Trainable model with $\frac{1}{p}{\rm
tr}{\bf C}^{\circ}=0.16$, $b)$ SW with $\frac{1}{p}{\rm tr}{\bf
C}^{\circ}=0.04$ and $c)$ Fixed model with $\frac{1}{p}{\rm tr}{\bf
C}^{\circ}=0.01$.

###  3.2 Practical implications for transfer learning

We first illustrate the observations in the previous section in a transfer
regression setup. The goal is to show that, in that scenario, linear random
features (i.e., $\sigma(t)=t$) transfer better than non-linear random features
(i.e., $\sigma(t)\neq t$). We train the ResNet50 (RN50) model on the source
domain dataset $S$ (ImageNet) [15]. We then extract features from images of
the target domain $T$ (STL dataset) [16]. We then apply a regression model on
$\sigma({\bf WX})$ with polynomial activation function
$\sigma(t)=a_{2}t^{2}+t$ to the target features. Figure 2 shows the test Mean
Squared Error (MSE) as a function of $a_{2}$ 111Note that for a polynomial
activation function $\sigma(t)=a_{2}t^{2}+a_{1}t,$ $d_{1}=a_{1}^{2}$ and
$d_{2}=2a_{2}^{2}$.. We can see from Figure 2 that the linear activation is
optimal when using the _expressive_ feature extractor RN50.

Next, we consider transfer learning experiments on DNN models. Our transfer
learning framework follows the illustration in Figure 1. A DNN model was
pretrained on a source dataset $S$ using two strategies: $i)$ classical
pretraining where a linear classifier is trained along the DNN’s backbone;
$ii)$ only the backbone is trained with the classifier fixed as a linear
random layer following ETF geometry. We then finetune the pretrained model on
a target dataset $T.$ We conducted a series of experiments to evaluate the
transferability of DNNs trained with fixed ETF classifiers. Our main objective
is to demonstrate the superior performance of these models when transferring
to new domains, especially when dealing with out-of-distribution datasets.

We employed two DNN architectures: ResNet50 and ResNet101, and pretrained them
on the popular ImageNet dataset. Subsequently, we performed transfer
experiments on the following target datasets: CIFAR100 [17], CIFAR10 [17],
STL10 [16], Oxford Pets [18], Oxford Flowers [19], DTD [20], SVHN [21].

We pretrained both ResNet50 and ResNet101 [22] backbones using three different
strategies:

  1. 1.

Trainable Model: Training with a trainable linear classifier.

  2. 2.

SW: Training with the Switchable Whitening [6] method that explicitly whiten
class covariances during pretraining.

  3. 3.

Fixed Model (Ours): Training with a fixed ETF classifier, enforcing class
separation through implicit minimization of class covariances.

RN50 models were trained for $180$ epochs and RN101 were pretrained for $100$
epochs with an initial learning rate of 0.01, a batch size of 128, momentum of
0.9, and weight decay of $2\times 10^{-4}$. We applied standard data
augmentation and normalization for each corresponding dataset.

For the transfer learning experiments, we fine-tuned each model on the target
datasets, starting from the checkpoint of the aforementioned methods. Table 1
summarizes the results of these experiments.

Table 1: Analyses for transfer learning using RN50/RN101 models pretrained on the ImageNet (Source S) and finetuned on the transfer datasets (Target T). | Transfer data | Model | RN50 | RN101 |
---|---|---|---|---|---
In Domain | ImageNet (S) | Trainable Model | $75.25$ | ${\bf 79.20}$ |
SW | ${\bf 77.93}$ | $79.13$ |
| Fixed Model (ours) | $76.72$ | $77.29$ |
CIFAR100 (T) | Trainable Model | $61.59$ | $59.86$ |
SW | ${\bf 62.55}$ | $60.30$ |
Fixed Model (ours) | $62.33$ | ${\bf 62.38}$ |
CIFAR10 (T) | Trainable Model | ${\bf 89.56}$ | $87.93$ |
SW | $88.68$ | ${\bf 88.43}$ |
Fixed Model (ours) | $89.33$ | $88.38$ |
STL10 (T) | Trainable Model | $60.03$ | $56.32$ |
SW | $63.32$ | $61.91$ |
| Fixed Model (ours) | ${\bf 63.73}$ | ${\bf 65.17}$ |
Out of Domain | SVHN (T) | Trainable model | $95.10$ | $95.56$ |
SW | ${\bf 95.67}$ | ${\bf 95.67}$ |
Fixed Model (ours) | $94.40$ | $95.02$ |
Pets (T) | Trainable Model | $40.50$ | $46.47$ |
SW | $39.22$ | $45.10$ |
Fixed Model (ours) | ${\bf 48.32}$ | ${\bf 53.17}$ |
Flowers (T) | Trainable model | $38.05$ | $37.09$ |
SW | $41.56$ | $44.07$ |
Fixed Model (ours) | ${\bf 60.30}$ | ${\bf 57.03}$ |
DTD (T) | Trainable model | $29.09$ | $28.24$ |
SW | $24.62$ | $30.74$ |
Fixed Model (ours) | ${\bf 40.90}$ | ${\bf 34.68}$ |

The results presented in Table 1 highlight the effectiveness of utilizing DNN
models trained with fixed ETF classifiers for transfer learning tasks. We have
split the results into “In-domain" and “Out-Of-Domain" categories to showcase
the difference in accuracy of models between both domain-specific and domain-
agnostic transfer learning tasks.

In-Domain Transfer: The three models achieve comparable accuracy. When the
source dataset $S$ and target dataset $T$ have lower domain shift, minimizing
the class covariances during adaptation will have a small effect as the class-
covariances of the similar source domain data have already been made
negligeable during pretraining.

Out-Of-Domain Transfer: Here, our approach consistently outperforms the
baseline methods across all datasets and architectures, with a gain of up to
$19\%$ compared to the SW [6] method. This suggests that the model excels at
adapting to different and unrelated data distributions. When the source domain
$S$ has already undergone the implicit minimization of class covariances, the
fine-tuned model benefits from this property. In out-of-distribution domains,
class covariances can significantly vary from the source domain. By implicitly
minimizing these covariances during training, the model becomes more robust to
domain shifts. It will tend to focus more on relevant features for class
separation rather than domain-specific covariances. This is highlighted in
Figure 3 where the covariance ${\bf C}^{\circ}{}$ of the extracted features
from the finetuned model is closer to ${\bf 0}$ for the fixed ETF model than
it is for the baseline models (_Trainable_ and _SW_).

##  4 Conclusion

In this paper, we have investigated the concept of utilizing DNN models
trained with fixed random classifiers for enhanced transferability in
downstream tasks. We have shown that a random projector with a linear
activation function, applied to features extracted from DNN models, offers
strong transfer performances especially in scenarios involving out-of-
distribution domains, on a range of fine-grained image classification tasks.
By implicitly minimizing class covariances during pretraining, the models tend
to focus on essential features for class separation, reducing dependency on
domain-specific variations. This work provides a practical strategy for
improving transfer learning on challenging out-of-distribution target domains,
opening up avenues for future research in advancing the state-of-the-art on
transfer learning with “foundation models".

## References

  * [1] Jianfeng Lu and Stefan Steinerberger,  “Neural collapse with cross-entropy loss,”  arXiv:2012.08465, 2020.
  * [2] Yibo Yang, Shixiang Chen, Xiangtai Li, Liang Xie, Lin Zhouchen, and Dacheng Tao,  “Inducing neural collapse in imbalanced learning: Do we really need a learnable classifier at the end of deep neural network,”  NeurIPS, vol. 35, pp. 37991–38002, 2022.
  * [3] Yibo Yang, Haobo Yuan, Xiangtai Li, Zhouchen Lin, Philip Torr, and Dacheng Tao,  “Neural collapse inspired feature-classifier alignment for few-shot class incremental learning,”  arXiv:2302.03004, 2023.
  * [4] Vardan Papyan, XY Han, and David L Donoho,  “Prevalence of neural collapse during the terminal phase of deep learning training,”  PNAS, vol. 117, no. 40, pp. 24652–24663, 2020.
  * [5] Peifeng Gao, Qianqian Xu, Peisong Wen, Huiyang Shao, Zhiyong Yang, and Qingming Huang,  “A study of neural collapse phenomenon: Grassmannian frame, symmetry, generalization,”  arXiv:2304.08914, 2023.
  * [6] Xingang Pan, Xiaohang Zhan, Jianping Shi, Xiaoou Tang, and Ping Luo,  “Switchable whitening for deep representation learning,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019, pp. 1863–1871.
  * [7] XY Han, Vardan Papyan, and David L Donoho,  “Neural collapse under mse loss: Proximity to and dynamics on the central path,”  arXiv:2106.02073, 2021.
  * [8] Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu,  “A geometric analysis of neural collapse with unconstrained features,”  Advances in Neural Information Processing Systems, vol. 34, pp. 29820–29834, 2021.
  * [9] Ali Rahimi and Benjamin Recht,  “Random features for large-scale kernel machines,”  Advances in neural information processing systems, vol. 20, 2007\.
  * [10] Hafiz Tiomoko Ali, Zhenyu Liao, and Romain Couillet,  “Random matrices in service of ml footprint: ternary random features with no performance loss,”  arXiv:2110.01899, 2021.
  * [11] Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet,  “Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures,”  in ICML. PMLR, 2020, pp. 8573–8582.
  * [12] Hafiz Tiomoko Ali, Abla Kammoun, and Romain Couillet,  “Random matrix-improved kernels for large dimensional spectral clustering,”  in SSP, 2018, pp. 453–457.
  * [13] Zhenyu Liao and Romain Couillet,  “On inner-product kernels of high dimensional data,”  in CAMSAP. IEEE, 2019, pp. 579–583.
  * [14] Romain Couillet and Florent Benaych-Georges,  “Kernel spectral clustering of large dimensional data,”  Electronic Journal of Statistics, vol. 10, pp. 1393–1454, 2016\.
  * [15] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei,  “ImageNet: A Large-Scale Hierarchical Image Database,”  in CVPR, 2009.
  * [16] Adam Coates, Andrew Ng, and Honglak Lee,  “An analysis of single-layer networks in unsupervised feature learning,”  in AISTATS, 2011, pp. 215–223.
  * [17] Alex Krizhevsky, Geoffrey Hinton, et al.,  “Learning multiple layers of features from tiny images,”  2009\.
  * [18] Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and CV Jawahar,  “Cats and dogs,”  in CVPR. IEEE, 2012, pp. 3498–3505.
  * [19] M-E Nilsback and Andrew Zisserman,  “A visual vocabulary for flower classification,”  in CVPR. IEEE, 2006, vol. 2, pp. 1447–1454.
  * [20] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, , and A. Vedaldi,  “Describing textures in the wild,”  in Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2014.
  * [21] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng,  “Reading digits in natural images with unsupervised feature learning,”  2011\.
  * [22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in CVPR, 2016, pp. 770–778.


Nadia Flodgren

# One-loop RG flow for adjoint multiscalar gauge theory

###### Abstract

We study the one-loop renormalisation of 4d SU(N) Yang-Mills theory with $M$
adjoint representation scalar multiplets. We calculate the coupled one-loop
renormalization group flows for this theory by developing an algebraic
description, which we find to be characterised by a non-associative algebra of
marginal couplings. The 4d one-loop beta function of the gauge coupling
$g^{2}$ vanishes for the case $M=22$, which is intriguing for string theory.
There are real fixed flows (fixed points of $\lambda/g^{2}$) only for $M\geq
406$, rendering one-loop fixed points of the gauge coupling and scalar
couplings incompatible.

##  1 Introduction

Gauge interactions have been argued to be necessary for weakly coupled UV
fixed points in 4D QFTs [1, 2]. We study the one-loop RG flow of multiscalar
gauge theory in 4D at large N with massless adjoint scalars that interact
quartically. The adjoint scalar gauge theories are of interest due to their
use in describing the dynamics on branes in $D3-$brane theories in string
theory. In our model the adjoint scalar multiplets are invariant under $O(M)$
symmetry and the gauge group is $SU(N)$. The quartic interaction term is

$\mathcal{L}_{int}=-\frac{1}{4!}\lambda_{\bar{A}\bar{B}\bar{C}\bar{D}}\phi_{\bar{A}}\phi_{\bar{B}}\phi_{\bar{C}}\phi_{\bar{D}}.$
(1)

The multi-index $\bar{A}=aA$ where $a=1,\dots,M$ is the scalar multiplet index
and $A=1,\dots,N^{2}-1$ is the Lie algebra index.

This presentation is based on my work with Bo Sundborg [3].

##  2 Algebraic description of one-loop RG flow of adjoint multiscalar gauge
theory

The general one-loop beta functions for a multiscalar gauge theory are [4, 5]

$\begin{split}&\mu\frac{d}{d\mu}\lambda_{\bar{A}\bar{B}\bar{C}\bar{D}}=\beta_{\bar{A}\bar{B}\bar{C}\bar{D}}=\frac{1}{(4\pi)^{2}}\bigg{(}\Lambda_{\bar{A}\bar{B}\bar{C}\bar{D}}^{2}-3g^{2}\Lambda^{S}_{\bar{A}\bar{B}\bar{C}\bar{D}}+3g^{4}A_{\bar{A}\bar{B}\bar{C}\bar{D}}\bigg{)},\end{split}$
(2)

where

$\begin{split}&\Lambda^{2}_{\bar{A}\bar{B}\bar{C}\bar{D}}=\frac{1}{8}\sum_{\text{perms}}\lambda_{\bar{A}\bar{B}\bar{E}\bar{F}}\lambda_{\bar{E}\bar{F}\bar{C}\bar{D}}\\\
&\Lambda^{S}_{\bar{A}\bar{B}\bar{C}\bar{D}}=\sum_{i}C(i)\lambda_{\bar{A}\bar{B}\bar{C}\bar{D}}\\\
&A_{\bar{A}\bar{B}\bar{C}\bar{D}}=\frac{1}{8}\sum_{\text{perms}}\\{\theta^{E},\theta^{F}\\}_{\bar{A}\bar{B}}\\{\theta^{E},\theta^{F}\\}_{\bar{C}\bar{D}}.\end{split}$
(3)

The gauge coupling is called $g$, the sum over permutations is over the
permutations of the multi-indices, the sum over $i$ is over the external legs,
$C(i)$ is the quadratic Casimir $C_{2}(G)$ for the gauge group $G$ and
$\theta_{\bar{A}\bar{B}}^{C}$ is a reducible representation of the gauge Lie
algebra.

The one-loop beta functions for multiscalar gauge theory can be characterized
by an algebra, as described in more detail in our work [3]. We consider only
marginal quartic couplings $\lambda_{\bar{A}\bar{B}\bar{C}\bar{D}}$ and can
think of the couplings as a vector space. For a purely scalar theory the one-
loop beta function $\beta_{\lambda}$ is quadratic in $\lambda$, as is seen
from the scalar-scalar interaction term in (3). This allows us to define a
product of the marginal couplings

$\begin{split}\lambda\diamond\kappa&\equiv\frac{(4\pi)^{2}}{2}(\beta_{\lambda+\kappa}-\beta_{\lambda}-\beta_{\kappa}).\end{split}$
(4)

Here we ignored the gauge terms in the beta functions since they do not affect
the product. The product is commutative but not generally associative.

It is useful to express the algebra using a basis of symmetric rank four
tensor structures $g^{k}_{\bar{A}\bar{B}\bar{C}\bar{D}}$ where
$\lambda_{\bar{A}\bar{B}\bar{C}\bar{D}}=\lambda_{k}g^{k}_{\bar{A}\bar{B}\bar{C}\bar{D}}$.
The basis elements $g^{k}_{\bar{A}\bar{B}\bar{C}\bar{D}}$ are the tensor
structures of the marginal operators of the theory, i.e. the quartic
invariants (indexed by $k$). The beta function is
$\beta_{\bar{A}\bar{B}\bar{C}\bar{D}}=\beta_{k}g^{k}_{\bar{A}\bar{B}\bar{C}\bar{D}}$
where $\beta_{k}=\frac{d\lambda_{k}}{d\ln(\mu)}$. We define the product

$\begin{split}\left(g^{m}\diamond
g^{n}\right)_{\bar{A}\bar{B}\bar{C}\bar{D}}=\frac{1}{8}\sum_{\text{perms}}g^{m}_{\bar{A}\bar{B}\bar{E}\bar{F}}g^{n}_{\bar{E}\bar{F}\bar{C}\bar{D}}=C^{mn}_{k}g^{k}_{\bar{A}\bar{B}\bar{C}\bar{D}}.\end{split}$
(5)

The coefficients $C^{mn}_{k}$ are the structure constants of the algebra. The
product is known as the $\vee$-product in [6]. The beta function is

$\begin{split}(4\pi)^{2}\beta_{k}=(\lambda_{m}\lambda_{n}C^{mn}_{k}-3g^{2}C_{1}\lambda_{k}+3g^{4}d_{k}),\\\
\end{split}$ (6)

where $d_{k}$ are the coefficients of the gauge induced term and
$C_{1}=4C_{2}(G)$.

Let us study the specific example of our $SU(N)\times O(M)$ model, which has
four quartic invariants indexed by $k=1s,1t,2s,2t$. They correspond to the
symmetric tensor structures via111Note that we will from now on suppress the
multi-indices when writing the basis elements
$g^{k}_{\bar{A}\bar{B}\bar{C}\bar{D}}\rightarrow g^{k}$.

$\displaystyle\frac{1}{4!}g_{\bar{A}\bar{B}\bar{C}\bar{D}}^{1s}\phi_{\bar{A}}\phi_{\bar{B}}\phi_{\bar{C}}\phi_{\bar{D}}$
$\displaystyle=\frac{1}{2}\operatorname{Tr}\Phi_{a}\Phi_{a}\Phi_{b}\Phi_{b}$
(7)
$\displaystyle\frac{1}{4!}g_{\bar{A}\bar{B}\bar{C}\bar{D}}^{1t}\phi_{\bar{A}}\phi_{\bar{B}}\phi_{\bar{C}}\phi_{\bar{D}}$
$\displaystyle=\frac{1}{4}\operatorname{Tr}\Phi_{a}\Phi_{b}\Phi_{a}\Phi_{b}$
$\displaystyle\frac{1}{4!}g_{\bar{A}\bar{B}\bar{C}\bar{D}}^{2s}\phi_{\bar{A}}\phi_{\bar{B}}\phi_{\bar{C}}\phi_{\bar{D}}$
$\displaystyle=\frac{1}{2}\operatorname{Tr}\Phi_{a}\Phi_{a}\operatorname{Tr}\Phi_{b}\Phi_{b}$
$\displaystyle\frac{1}{4!}g_{\bar{A}\bar{B}\bar{C}\bar{D}}^{2t}\phi_{\bar{A}}\phi_{\bar{B}}\phi_{\bar{C}}\phi_{\bar{D}}$
$\displaystyle=\operatorname{Tr}\Phi_{a}\Phi_{b}\operatorname{Tr}\Phi_{a}\Phi_{b},$

where $\Phi_{a}=\phi_{\bar{A}}T_{A}$ belongs to the adjoint representation and
$T_{A}$ is matrix in the fundamental representation222We use the normalization
$\operatorname{Tr}(T_{A}T_{B})=\frac{1}{2}\delta_{AB}$ of the fundamental
representation matrices $T_{A}$.. The superscripts $s$ and $t$ stand for
scalar and tensor product respectively, and $1$ and $2$ stand for single-trace
and double-trace respectively.

To take the large $N$ limit of the algebra for $g^{k}$ we must first rescale
the couplings $\lambda_{k}$ in order to keep the ’t Hooft couplings
$\lambda_{K}$ constant: $\lambda_{1S}=N\lambda_{1s}$,
$\lambda_{1T}=N\lambda_{1t}$ and $\lambda_{2S}=N^{2}\lambda_{2s}$,
$\lambda_{2T}=N^{2}\lambda_{2t}$. The basis elements $g^{k}$ are rescaled to
$g^{K}$ accordingly to keep $\lambda_{k}g^{k}=\lambda_{K}g^{K}$ constant.
Taking the large $N$ limit and dropping sub-leading terms simplifies the
algebra. The algebra at large $N$ for the basis $g^{K}$ is

$\displaystyle g^{1S}\diamond g^{1S}$
$\displaystyle=\frac{1}{2}(M+3)g^{2S}+\frac{1}{2}g^{2T}+\frac{1}{2}(M+3)g^{1S}$
(8) $\displaystyle g^{1T}\diamond g^{1T}$
$\displaystyle=\frac{1}{8}(M+2)g^{2T}+\frac{1}{2}g^{1S}$ $\displaystyle
g^{1S}\diamond g^{1T}$
$\displaystyle=\frac{1}{2}g^{2S}+\frac{1}{2}g^{2T}+\frac{1}{2}g^{1S}+g^{1T}$
$\displaystyle g^{2S}\diamond g^{2S}$ $\displaystyle=Mg^{2S}$ $\displaystyle
g^{2T}\diamond g^{2T}$ $\displaystyle=2g^{2T}$ $\displaystyle g^{2S}\diamond
g^{2T}$ $\displaystyle=2g^{2S}$ $\displaystyle g^{1S}\diamond g^{2S}$
$\displaystyle=(M+1)g^{2S}$ $\displaystyle g^{1S}\diamond g^{2T}$
$\displaystyle=2g^{2S}+g^{2T}$ $\displaystyle g^{1T}\diamond g^{2S}$
$\displaystyle=g^{2S}$ $\displaystyle g^{1T}\diamond g^{2T}$
$\displaystyle=g^{2T}.$

The large $N$ algebra has several closed sub-algebras,
$\\{g^{2S}\\},\\{g^{2T}\\},\\{g^{2S},g^{2T}\\},\\{g^{1S},g^{2S},g^{2T}\\}$,
and two ideals $\\{g^{2S}\\},\\{g^{2S},g^{2T}\\}$. The brackets $\\{\\}$
denote a linear space with the $\diamond$-product that is spanned by the
elements in the brackets. The algebra indicates which couplings induce running
in other couplings. For example, the closed sub-algebra $\\{g^{2T}\\}$
indicates that a theory with the only non-zero coupling333Note that the gauge
coupling or its coefficients $d_{K}$ in $\beta_{K}$ must also be vanishing
here. being $\lambda_{2T}$ is renormalizable in this limit. The ideals are
closed sub-algebras that are stable under perturbations of elements outside
the ideal. The sub-algebra $\\{g^{2S}\\}$ is an ideal because all products
with $g^{2S}$ in (8) result only in the element itself. Physically the beta
functions of the quotient algebra of an ideal are independent of the couplings
in the ideal, giving the RG equations a hierarchical structure.

##  3 Results: one-loop RG flow for adjoint multiscalar gauge theory

Let us take a look at the beta functions for our model. The one-loop beta
function for the gauge coupling vanishes for $M=22$ adjoint scalars

$\displaystyle\beta_{g}$
$\displaystyle=-\frac{g^{3}}{16\pi^{2}}\frac{22-M}{6}C_{2}(G).$ (9)

The RG flow is asymptotically UV free for $M<22$ and IR free for $M>22$. The
critical value of $M=22$ has been noted before in [7]. The critical value
intrigued us as it could indicate a string theory connection since $22$
adjoint scalars in 4D would correspond to a low energy limit of $N$ parallel
$D3$-branes in $26=22+4$ dimensions (the critical dimension of bosonic
strings).

From the algebra (8) we calculate the scalar coupling beta functions, apart
from the gauge induced terms which are calculated separately. We find no real
fixed points for $M=22$ scalars. In order to relate to possible fixed points
for a running gauge coupling we calculate the beta functions for the relative
couplings $\mu_{K}=\lambda_{K}/g^{2}$. A fixed point for a relative coupling
is called a fixed flow. The beta functions for the relative couplings at large
$N$ are

$\displaystyle\beta_{1S}(\mu)=$
$\displaystyle\frac{Ng^{2}}{16\pi^{2}}\left(\frac{M+3}{2}\mu_{1S}\mu_{1S}+\frac{1}{2}\mu_{1T}\mu_{1T}+\mu_{1T}\mu_{1S}-\left(\frac{M-22}{3}+12\right)\mu_{1S}+6\right)$
(10) $\displaystyle\beta_{1T}(\mu)=$
$\displaystyle\frac{Ng^{2}}{16\pi^{2}}\left(2\mu_{1T}\mu_{1S}-\left(\frac{M-22}{3}+12\right)\mu_{1T}\right)$
$\displaystyle\beta_{2S}(\mu)=$
$\displaystyle\frac{Ng^{2}}{16\pi^{2}}\left(M\mu_{2S}\mu_{2S}+\frac{(M+3)}{2}\mu_{1S}\mu_{1S}+4\mu_{2S}\mu_{2T}+2\mu_{2S}\mu_{1T}+2(M+1)\mu_{2S}\mu_{1S}\right.$
$\displaystyle\left.+4\mu_{2T}\mu_{1S}+\mu_{1T}\mu_{1S}-\left(\frac{M-22}{3}+12\right)\mu_{2S}+6\right)$
$\displaystyle\beta_{2T}(\mu)=$
$\displaystyle\frac{Ng^{2}}{16\pi^{2}}\left(2\mu_{2T}\mu_{2T}+\frac{1}{2}\mu_{1S}\mu_{1S}+\frac{M+2}{8}\mu_{1T}\mu_{1T}+2\mu_{2T}\mu_{1T}+2\mu_{2T}\mu_{1S}+\mu_{1T}\mu_{1S}\right.$
$\displaystyle\left.-\left(\frac{M-22}{3}+12\right)\mu_{2T}+6\right).$

Note that these beta functions are dependent on $M$ but independent of the
flow of the gauge coupling, meaning we can treat $g$ as a constant in
searching for fixed points of the relative couplings.

In the beta functions (10) we can observe the implication of the quotient
algebra of the double-trace ideal $\\{g^{2S},g^{2T}\\}$, i.e. that
$\beta_{1S}$ and $\beta_{1T}$ are independent of the double-trace couplings
$\lambda_{2S},\lambda_{2T}$, and the implication of the ideal $\\{g^{2S}\\}$,
which is that only $\beta_{2S}$ depends on $\lambda_{2S}$.

In the space of single-trace couplings $(\lambda_{1S},\lambda_{1T})$ there are
real fixed flows only for $M\geq 82$, for which there exists one UV-stable and
one mixed stability fixed flow, see Figure 1(a).

(a) Single-trace RG flow for $M=425$.

(b) Double-trace RG flow for $M=425$.

Figure 1: The RG flow for $M=425$ in the single-trace space 1(a) and double-
trace space 1(b). The single-trace space has one UV stable fixed flow (purple
dot) and one of mixed stability (green dot). The double-trace space has four
fixed flows (two for each blue dot) which are shown in Figure 2.

The RG flow of the double-trace coupling space $(\lambda_{2S},\lambda_{2T})$
is seen in Figure 1(b) and 2. In this space there are only real fixed flows
for $M\geq 406$. In the range $406\leq M\leq 427$ there are four real fixed
flows (one IR stable, one UV stable and two of mixed stability) and for $M\geq
428$ there are eight real fixed flows.

(a) Double-trace RG flow for $M=425$, lower feature.

(b) Double-trace RG flow for $M=425$, upper feature.

Figure 2: Double-trace RG flow for $M=425$. The lower feature has one UV
stable fixed flow and one of mixed stability. The upper feature has one IR
stable fixed flow (red dot) and one of mixed stability. Together the four
fixed flows form a parallelogram which no flow can escape.

In conclusion, the RG flow of the complete space of marginal quartic couplings
only has real fixed flows for $M\geq 406$, for which the gauge coupling is IR
free. Therefore, no complete gauge coupling and scalar coupling fixed point
exists for the adjoint multiscalar gauge theory at large $N$ to one-loop
order.

##  4 Outlook

So far we have only studied the regular large $N$ limit but there exists other
possible large $N$ limits we want to investigate, such as a Veneziano-like
limit where both $N$ and $M$ are large. We are interested in seeing whether
the algebra itself can tell us which limits have interesting RG flows.

Concerning the specific $SU(N)\times O(M)$ model we studied, one could
consider the case $M=22$ but for a complex CFT and look for stable complex
CFTs. The stability of the potential, in the sense of a theory bounded from
below, at the fixed points would then need to be checked.

The main unanswered question we have is if the algebraic description of the RG
flow can be adapter to higher loop orders. Related to this, we have also
thought about studying the RG flow of models with different fields and
interactions via the algebra, to see if the algebra can give new insights.
Generalizing out method should be fairly simple since it relies on very
general known one-loop equations.

## References

  * [1] S.R. Coleman and D.J. Gross, _Price of asymptotic freedom_ , _Phys. Rev. Lett._ 31 (1973) 851.
  * [2] A.D. Bond and D.F. Litim, _Price of Asymptotic Safety_ , _Phys. Rev. Lett._ 122 (2019) 211601 [1801.08527].
  * [3] N. Flodgren and B. Sundborg, _One-loop algebras and fixed flow trajectories in adjoint multi-scalar gauge theory_ , _JHEP_ 04 (2023) 129 [2303.13884].
  * [4] M.E. Machacek and M.T. Vaughn, _Two Loop Renormalization Group Equations in a General Quantum Field Theory. 3. Scalar Quartic Couplings_ , _Nucl. Phys. B_ 249 (1985) 70.
  * [5] M.-x. Luo, H.-w. Wang and Y. Xiao, _Two loop renormalization group equations in general gauge field theories_ , _Phys. Rev. D_ 67 (2003) 065019 [hep-ph/0211440].
  * [6] L. Michel and L.A. Radicati, _Properties of the breaking of hadronic internal symmetry_ , _Annals Phys._ 66 (1971) 758.
  * [7] T.L. Curtright, _Charge Renormalization and High Spin Fields_ , _Phys. Lett. B_ 102 (1981) 17.