# Block designs and prime values of polynomials

Gareth A. Jones and Alexander K. Zvonkin  School of Mathematical Sciences,
University of Southampton, Southampton SO17 1BJ, UK
<EMAIL_ADDRESS>LaBRI, Université de Bordeaux, 351 Cours de la
Libération, F-33405 Talence Cedex, France<EMAIL_ADDRESS>
###### Abstract.

A recent construction by Amarra, Devillers and Praeger of block designs with
specific parameters depends on certain quadratic polynomials, with integer
coefficients, taking prime power values. The Bunyakovsky Conjecture, if true,
would imply that each of them takes infinitely many prime values, giving an
infinite family of block designs with the required parameters. We have found
large numbers of prime values of these polynomials, and the numbers found
agree very closely with the estimates for them provided by Li’s recent
modification of the Bateman–Horn Conjecture. While this does not prove that
these polynomials take infinitely many prime values, it provides strong
evidence for this, and it also adds extra support for the validity of the
Bunyakovsky and Bateman-Horn Conjectures.

###### Key words and phrases:

block design, polynomial, prime number, Bateman–Horn Conjecture, Bunyakovsky
Conjecture

###### 2010 Mathematics Subject Classification:

05B05, 11N32

##  1\. Introduction

Block designs play a major role in combinatorics and finite geometry, and have
many applications in statistics, specifically in the design of experiments. In
[2], Amarra, Devillers and Praeger have recently constructed families of
highly symmetric $2$-designs which maximise certain parameters. Their
constructions depend on certain quadratic polynomials with integer
coefficients taking prime power values. Many of their polynomials satisfy
three simple necessary conditions which Bunyakovsky [6] in 1857 conjectured
were also sufficient for any polynomial to take infinitely many prime values.
Unfortunately, this conjecture has been proved only for polynomials of degree
$1$ (Dirichlet’s Theorem on primes in an arithmetic progression).
Nevertheless, the Bateman–Horn Conjecture [4], dating from 1962 and also
proved only for degree $1$, gives estimates $E(x)$ for the number $Q(x)$ of
positive integers $t\leq x$ at which a given polynomial takes prime values.
Using a recent improvement to the Bateman–Horn Conjecture due to Li [22], we
calculated these estimates $E(x)$ for some of the simpler polynomials arising
in [2], taking $x=10^{8}$, and compared them with the actual numbers $Q(x)$
found by computer searches. As in various other applications of this
conjecture (see [19, 20] for example), the estimates $E(x)$ are remarkably
close to the actual values $Q(x)$. Although this does not prove the existence
of infinite families of block designs, the accuracy of the estimates, together
with the abundance of examples found, provides strong evidence for it, and it
also adds to the growing body of evidence in favour of the more general
Bunyakovsky and Bateman–Horn Conjectures.

There have been many number-theoretic applications of the Bateman–Horn
Conjecture (see [1] for a survey), and a handful in areas such as
combinatorics [14], cryptography [7, 26, 27, 28], elliptic curves [3, 12],
error-correcting codes [21] and fast integer multiplication [11]. It seems
likely that the present paper and [2] represent its first application to block
designs, just as [19, 20] are the first in the areas of dessins d’enfants and
permutation groups.

##  2\. Primes versus prime powers

Although the problem in [2] requires prime power values of certain polynomials
$f_{n,r}(t)\in{\mathbb{Z}}[t]$, it is easier to estimate the distribution of
their prime values, using the Prime Number Theorem and conjectures based on
it. This restriction is no great loss, as the vast majority of prime powers,
up to any given large bound, are in fact prime: if $\pi(x)$ is the usual
function counting primes $p\leq x$, and $\Pi(x)$ is its analogue for prime
powers $p^{e}\leq x$, then $\pi(x)/\Pi(x)\to 1$ (quite rapidly) as
$x\to\infty$. For example,
$\pi(10^{6})/\Pi(10^{6})=78\,498/78\,734=0.9970002\ldots$, while
$\pi(10^{9})/\Pi(10^{9})=50\,847\,534/50\,851\,223=0.999927\ldots$ (see [10]).
Nevertheless, we carried out a more restricted search, over
$t=1,\ldots,10^{7}$, for prime power values $f_{n,r}(t)$ of the chosen
polynomials, finding just a few squares and one cube (see Section 12).
However, in Section 14 we show how to realise any even power $p^{2i}>9$ of an
odd prime $p$ as $f_{n,r}(0)$ for some polynomial $f_{n,r}$, a situation which
has some interest for the construction of block designs.

##  3\. The Bunyakovsky Conjecture

If a non-costant polynomial $f(t)\in{\mathbb{Z}}[t]$ is to take infinitely
many prime values for $t\in{\mathbb{N}}$ (equivalently, if it is prime for
infinitely many such $t$), then the following conditions must be satisfied:

  * (a)

$f$ must have a positive leading coefficient (otherwise it will take only
finitely many positive values);

  * (b)

$f$ must be irreducible in ${\mathbb{Z}}[t]$ (otherwise all but finitely many
of its values will be composite);

  * (c)

$f$ must not be identically zero modulo any prime $p$ (otherwise all its
values will be divisible by $p$).

In 1857 Bunyakovsky [6] conjectured that these three necessary conditions are
also sufficient. (Condition (c) is needed to avoid examples such as
$t^{2}+t+2$, which satisfies (a) and (b) but takes only even values.) For
instance, if this were true it would imply Landau’s conjecture (studied also
by Euler [15]) that there are infinitely many primes of the form $t^{2}+1$.
However, the Bunyakovsky Conjecture has been proved only in the case where $f$
has degree $1$: this is Dirichlet’s Theorem, that if $a$ and $b$ are coprime
integers then there are infinitely many primes of the form $at+b$ (see [5,
§5.3.2] for a proof).

##  4\. The Bateman–Horn Conjecture

In 1962 Bateman and Horn [4] proposed a very general conjecture (in what
follows we will use the abbreviation BHC) which comprises many previous
conjectures and theorems and gives quantified versions of them. It deals with
a finite set of polynomials simultaneously taking prime values. Though for our
purposes it is sufficient to consider the case of a single polynomial, we give
here the full version of the BHC. If we incorporate a recent improvement due
to Li [22], we get the following statement:

######  Conjecture 4.1 (Bateman and Horn, 1962; Li, 2019).

Let $f_{1},\ldots,f_{k}\in\mathbb{Z}[t]$ be coprime polynomials satisfying
conditions (a) and (b) of the Bunyakovsky Conjecture, and let their product
$f=f_{1}\cdots f_{k}$ satisfy condition (c). Denote by $Q(x)$ the number of
$t\in\mathbb{N}$, $t\leq x$, such that all $f_{i}(t)$, $i=1,\ldots,k$, are
prime. Then the asymptotic estimate $E(x)$ for the number $Q(x)$ is given by
the following formula:

(1) $Q(x)\sim
E(x):=C\negthinspace\int_{a}^{x}\negthinspace\frac{dt}{\prod_{i=1}^{k}\ln
f_{i}(t)}\quad\hbox{as}\quad x\to\infty$

where

(2)
$C=C(f):=\prod_{p}\left(1-\frac{1}{p}\right)^{-k}\left(1-\frac{\omega_{f}(p)}{p}\right)$

with the product over all primes $p$, and where $\omega_{f}(p)$ is the number
of congruence classes $t\in{\mathbb{Z}}_{p}$ such that $f(t)=0$. In (1), one
chooses $a\geq 2$ large enough that the range of integration avoids
singularities, where some $f_{i}(t)=1$. (In our applications we can always
take $a=2$.)

######  Lemma 4.2 (Constant $C(f)$).

The product in (2) converges to a constant $C>0$.

This statement is far from trivial. Bateman and Horn, in their original paper
[4], limit themselves to a few hints. The first detailed proof was recently
published in [1, Theorem 5.4.3], and it takes seven pages.

Since the integral in (1) diverges, we get the following

######  Corollary 4.3 (Infinitely many prime values).

The estimate $E(x)\to\infty$ as $x\to\infty$; therefore, $Q(x)$ also goes to
infinity: there are infinitely many integers $t\in\mathbb{N}$ such that all
$f_{i}(t)$, $i=1,\ldots,k$, are simultaneously prime.

As in the case of the Bunyakovsky Conjecture, the BHC, even when restricted to
a single polynomial $f$, has been proved only in the case where $\deg f=1$.
This is the quantified version of Dirichlet’s Theorem, that for fixed coprime
$a$ and $b$ the number of $t\leq x$ such that $at+b$ is prime is asymptotic to

$\frac{1}{\varphi(a)}\int_{2}^{x}\frac{dt}{\ln(at+b)},$

where $\varphi$ is Euler’s totient function. (Equivalently, the primes in the
arithmetic progression $at+b$ are asymptotically equally distributed among the
$\varphi(a)$ congruence classes of units mod $a$; see [5, §5.3.2] for a
proof.)

An earlier special case of the BHC, applicable to a single quadratic
polynomial $f$, is the Conjecture F of Hardy and Littlewood [16], giving
similar estimates. For this reason, the constants $C(f)$ are sometimes known
as Hardy–Littlewood constants.

##  5\. Heuristic argument for the ingredients of the Bateman–Horn Conjecture

Here we give a heuristic argument to explain certain ingredients of the
formula (1) for the Bateman–Horn estimate $E(x)$.

The Prime Number Theorem provides two asymptotic estimates for the number
$\pi(x)$ of primes $p\leq x$ as $x\to\infty$, namely

(3) $\pi(x)\sim\frac{x}{\ln x}\quad\quad\hbox{and}\quad\quad\pi(x)\sim{\rm
Li}(x):=\int_{2}^{x}\frac{dt}{\ln t}.$

The first is easy to use, but not very accurate; the second, involving the
offset logarithmic integral function ${\rm Li}(x)$, is harder to use but much
more accurate. For example, the number of primes up to $10^{25}$ was computed
in 2013 by J. Buethe, J. Franke, A. Jost, and T. Kleinjung (see [24]): it is
equal to $\pi(10^{25})=176\,846\,309\,399\,143\,769\,411\,680$. The formula
$x/\ln x$ approximates this number with the relative error $-1.77\%$, while
the relative error of the estimate ${\rm Li}(10^{25})$ is $3.12\cdot
10^{-11}\%$.

In either case, (3) suggests that one can regard $1/\ln x$ as the probability
that $x$ (or, rather, a randomly-chosen number close to $x$) is prime.
Consider the “random variables” $\xi_{i}(t)=1$ if $f_{i}(t)$ is prime, and
$\xi_{i}(t)=0$ otherwise. The “probability” that $\xi_{i}(t)=1$ is $1/\ln
f_{i}(t)$. If, in addition, we presume that these variables, for any given
$t$, are independent, then the probability that all $f_{i}(t)$ are prime, or,
in other words, the probability that the product
$\eta(t):=\xi_{1}(t)\cdots\xi_{k}(t)$ is equal to $1$, is $\displaystyle
P(t)=\frac{1}{\prod_{i=1}^{k}\ln f_{i}(t)}$. Notice that the mean value of
$\eta(t)$ is the expected value ${\rm E}(\eta(t))=P(t)$.

The random variable $\eta(t)$ is a “counting function”: as a first estimate
for the number of $t\leq x$ such that all $f_{i}(t)$ are prime, we may take
the average number of times this variable is equal to 1. Let us choose $a$ so
that all $f_{i}(t)>1$ for $t\geq a$. Then, as $t$ goes from $a$ to $x$, we
have

(4) ${\rm E}\left(\sum_{t=a}^{x}\eta(t)\right)=\sum_{t=a}^{x}{\rm
E}(\eta(t))=\sum_{t=a}^{x}P(t)\approx\int_{a}^{x}P(t)dt=\int_{a}^{x}\frac{dt}{\prod_{i=1}^{k}\ln
f_{i}(t)}.$

We cannot present any profound reasons for considering
$f_{1}(t),\ldots,f_{k}(t)$ as independent for any given $t$, but at least this
assumption stands the test of a great number of experiments. However, the same
is not true when we vary the variable $t$. Therefore, a correcting term may be
needed, and this is the constant $C(f)$.

First, if $f(t_{0})\equiv 0$ mod $(p)$ for some integer $t_{0}$ and prime $p$,
then $f(t)\equiv 0$ mod $(p)$ for all $t\equiv t_{0}$ mod $(p)$. We would like
to avoid the situation when $f(t)$ is divisible by $p$ (or, equivalently, at
least one of $f_{i}(t)$ is divisible by $p$). The “probability” of the
opposite event is $a_{p}=1-\frac{\omega_{f}(p)}{p}$.

Second, the probability that a “randomly chosen” $k$-tuple of integers
(whatever that means) does not contain any element divisible by $p$ is
$b_{p}=\left(1-\frac{1}{p}\right)^{k}$. The ratio $a_{p}/b_{p}$ used in the
product (2) resembles the conditional probability, though it is not one since
it may well be $>1$.

What remains is to assemble different parts of this Lego, but the
corresponding procedure will need a long discussion and a self-coherent
construction of a “probabilistic model” of what takes place, so we stop here.
Anyway, we are not supposed to give a proof of the BHC; we only provide some
plausible speculations on the matter. “The proof of the pudding is in its
eating”: the conjecture works well, even surprisingly well, and this is what
is important about it.

The BHC is a statement involving a $k$-tuple of polynomials
$f_{1},\ldots,f_{k}$. In what follows we will work with a single polynomial,
so that $k=1$, and $f_{1}$ will from now on be denoted by $f$. There is no
contradiction with the previous notation where $f$ denoted the product of the
polynomials $f_{i}$.

##  6\. The constant $C(f)$

Computing the constant $C(f)$ is a challenging problem in itself. As already
mentioned above, the mere existence of a limit is a non-trivial fact. By the
way, the convergence is not absolute: by changing the order of factors we may
get a different limit value. This is perhaps one of the manifestations of the
fact that the “probabilistic measure” on $\mathbb{N}$ represented by the
density is finitely additive but not countably additive. To make matters
worse, the rate of convergence is, as one of our colleagues has put it,
“frustratingly slow”.

In Section 9 we discuss the computation of $\omega_{f}(p)$ for a single
quadratic polynomial $f$. We will see that it involves rather subtle number-
theoretic methods, mainly the quadratic reciprocity law. The case of cubic
polynomials is treated in [29].

A highly advanced method, though still for a single polynomial, was proposed
by H. Cohen [9]. For a quadratic polynomial it involves the techniques of
$L$-functions and, in particular, of the Riemann $\zeta$-function. For
polynomials of degree greater than 2 one also needs to know the Galois group
of the polynomial in question as well as the irreducible representations of
this group. An intermediate way is chosen by Li [22] (with a reference to K.
Conrad): he also uses $L$-functions but in a simpler way than in [9].

We have no intention to compete with the above specialists. Therefore, we have
computed the products only over primes $p\leq 10^{8}$. The constants $C(f)$
thus obtained already give excellent results in approximating the numbers of
prime values of the polynomials we study in this paper.

Another interesting question is, how large (or how small) the constant $C(f)$
could be. For example, for the well-known Euler polynomial $t^{2}+t+41$
(taking prime values for $t=0,1,2,\ldots,39$) the constant found in [9] is
$3.31977318$, while for the polynomial $t^{2}+t+75$ it is $0.31097668$ (in
fact, the author gives 39 correct digits for both numbers). Since the
integrals $\displaystyle\int_{2}^{x}\frac{dt}{\ln f(t)}$ for these two
polynomials are very close to each other for large $x$, we conclude that the
first polynomial produces, approximately, $10.7$ times as many primes as the
second one.

In [1], an example of a polynomial $f(t)=t^{2}+t+a$ is given, with the
constant $5.4972\ldots$. In this example, the coefficient $a$ is a 219-digit
number. This number is not prime, and the discriminant is not prime either. We
did not try to factorize them.

A more systematic search was carried out in [17] (which contains many
interesting examples) and [25] (which is, mostly, an experimental work). The
champion, found by Rivin, among the monic quadratic polynomials is
$t^{2}-2619t+1291$, with the corresponding constant equal to $6.3722$. The
discriminant of this polynomial is $6\,853\,997$, which is a prime. The author
has also found a monic polynomial of degree 6 with a yet greater constant
$C(f)$; the discriminant of the polynomial in question is $53\times\mbox{(a
prime with 37 digits)}$. The data based on a large random sample of monic
polynomials $f$ with their coefficients bounded by a large constant $N$
suggest that $C(f)$ obeys the log-normal distribution. If this observation
turns out to be true then, in general, $C(f)$ is unbounded. Other plausible
observations based on the experimental data are as follows: (a) the mean value
of $C(f)$ is 1; (b) for monic polynomials whose coefficients (other than the
leading one) are bounded by $N$, the maximum value of $C(f)$ grows like
$C(f)=O(\log\log N)$. At the same time, in [17] it is conjectured that among
the polynomials of the type $f(t)=t^{2}+t-a$ the maximum value of $C(f)$ is
equal to $5.65726388$, and it is attained for the 71-digit number

$a=33\,251\,810\,980\,696\,878\,103\,150\,085\,257\,129\,508\,857\,312\,847\,751\,498\,190\,{349\,983\,874\,538\,507\,313.}$

Finally, an example of a non-monic polynomial (also from [25]): taking
$f(t)=At^{2}+1$ with $A=\prod_{i=1}^{30}p_{i}$ the product of the first 30
primes from $p_{1}=2$ to $p_{30}=113$, we get a rather large constant
$C(f)\approx 9.5$. There is no mystery: all the factors $(1-1/p)^{-1}$ in (2)
are greater than 1, while $\omega_{f}(p)=0$ for $p=2,3,\ldots,113$ (in fact,
also for $p=127$ but not for 131), making the factors $(1-\omega_{f}(p)/p)$
equal to 1, so that they do not compensate for a steadily growing product
which reaches, at this initial stage, approximately $8.78$.

##  7\. Block designs

Here, in order to provide motivation for our particular choice of polynomials
$f$, we briefly summarise the construction in [2] of block designs requiring
certain polynomials to take prime power values. Readers who are interested
only in the number-theoretic aspects of this problem can safely omit this
section.

A 2-$(v,k,\lambda)$ design $\mathcal{D}$ consists of a set $\mathcal{P}$ of
$v$ points, together with a set $\mathcal{B}$ of $k$-element subsets of
$\mathcal{P}$ called blocks, such that each pair of points lie in exactly
$\lambda$ blocks. (This implies that each point lies in the same number of
blocks.) The automorphisms of $\mathcal{D}$ are the permutations of
$\mathcal{P}$ which leave the set $\mathcal{B}$ invariant; they form a group
${\rm Aut}\,{\mathcal{D}}$.

If a subgroup $G\leq{\rm Aut}\,{\mathcal{D}}$ acts transitively on blocks then
it also acts transitively on points. The latter action could be imprimitive,
leaving invariant a partition $\mathcal{C}$ of $\mathcal{P}$ with $d\geq 2$
classes, each of size $c\geq 2$, so that $cd=v$. Delandtsheer and Doyen showed
in [13] that in this case there exist positive integers $m$ and $n$ such that

$mc+n=\binom{k}{2}=nd+m.$

These integers $m$ and $n$ are the Delandtsheer-Doyen parameters of
$\mathcal{D}$, with $n$ and $mc$ the numbers of unordered pairs of points in
any given block, lying in the same or in different classes of $\mathcal{C}$.

In [2], Amara, Devillers and Praeger have explored the restrictions these
parameters place on subgroups $G$ of ${\rm Aut}\,\mathcal{D}$. Let $K$ denote
the permutation group of degree $d$ induced by $G$ on the set of classes in
$\mathcal{C}$, and let $H$ be the permutation group of degree $c$ induced on
any class in $\mathcal{C}$ by its setwise stabiliser in $G$, so that $G$ is
embedded in the wreath product $H\wr K\leq{\rm S}_{c}\wr{\rm S}_{d}$. The rank
${\rm Rank}(X)$ of any transitive permutation group $X$ on a set $\Omega$ is
the number of orbits of a point-stabiliser $X_{\alpha}\;(\alpha\in\Omega)$, or
equivalently of $X$ on $\Omega\times\Omega$; similarly, the pair-rank ${\rm
PairRank}(X)$ is the number of orbits of $X$ on unordered pairs of distinct
elements of $X$, so that $({\rm Rank}(X)-1)/2\leq{\rm PairRank}(X)\leq{\rm
Rank}(X)-1$. The main result of [2] is that in the above circumstances

$\frac{{\rm Rank}(H)-1}{2}\leq{\rm PairRank}(H)\leq
n\quad\hbox{and}\quad\frac{{\rm Rank}(K)-1}{2}\leq{\rm PairRank}(K)\leq m.$

The authors of [2] give several constructions of designs $\mathcal{D}$ in
which the ranks and pair-ranks of $H$ and $K$ attain these upper bounds. One
construction requires useful pairs of integers $n,c$ with the properties that
$n\geq 2$ and $c$ is a prime power such that

$c\equiv 1\,{\rm mod}\,(2n)\quad\hbox{and}\quad c+n=\binom{k}{2}\;\,\hbox{for
some integer}\;\,k\geq 2n.$

They need $c$ to a prime power in order to define $H$ to be the unique
subgroup of index $n$ in ${\rm AGL}_{1}(c)$, acting naturally on the field
${\mathbb{F}}_{c}$, while they take $K={\rm S}_{d}$ acting naturally on
${\mathbb{Z}}_{d}$, so that $G:=H\wr K$ has a transitive but imprimitive
induced action on ${\mathcal{P}}={\mathbb{F}}_{c}\times{\mathbb{Z}}_{d}$ with
$d$ classes of size $c$. By taking $d=1+\frac{c-1}{n}$ (the number of orbits
of $H$ on ${\mathbb{F}}_{c}$) and defining ${\mathcal{B}}$ to be the set of
images under $G$ of a carefully-chosen $k$-element subset
$B\subset{\mathcal{P}}$ they obtain a 2-$(cd,k,\lambda)$ design $\mathcal{D}$
for some $\lambda$, admitting $G$ as a block-transitive and point-imprimitive
group of automorphisms. This design has Delandtsheer–Doyen parameters $m=1$
and $n$, with ${\rm Rank}(H)={\rm PairRank}(H)+1=n+1$ and ${\rm Rank}(K)={\rm
PairRank}(K)+1=2$.

The conditions for the pair $n,c$ to be useful imply that, if $r$ denotes the
least positive remainder of $k$ mod $(4n)$, then
$\binom{r}{2}\equiv\binom{k}{2}\equiv n+1$ mod $(2n)$. Thus, for fixed
positive integers $n\geq 2$ and $r<4n$ with $\binom{r}{2}\equiv n+1$ mod
$(2n)$ they need integers $k=4nt+r$ for some integer $t\geq 0$ such that

$f_{n,r}(t):=\binom{k}{2}-n=8n^{2}t^{2}+2n(2r-1)t+\left(\frac{r(r-1)}{2}-n\right)$

is a prime power $c$. If the polynomial $f_{n,r}$ takes prime power values for
infinitely many integers $t\geq 0$ then this construction yields an infinite
family of block designs with the required parameters and symmetry properties.

######  Example 7.1.

The smallest useful pair $(n,c)$ is $(2,13)$, with $r=k=6$ and $d=7$, so that
the corresponding design $\mathcal{D}$ has $cd=91$ points and $|G|=78^{7}\cdot
7!$ automorphisms. This example arises from the polynomial
$f_{n,r}(t)=f_{2,6}(t)=32t^{2}+44t+13$ taking the value $c=13$ at $t=0$. Note
that $f_{2,6}(1)=89$ is prime, giving a design on $cd=89\cdot 45=4005$ points,
whereas $f_{2,6}(2)=697=17\cdot 41$ is not a prime power and therefore does
not correspond to a design in this family.

The smaller polynomial $f_{2,3}(t)=32t^{2}+20t+1$ has its first prime power
value $f_{2,3}(1)=53$, giving a design on $53\cdot 27=1431$ points.

Note that, although this construction of block designs applies to any integer
$t\geq 0$ such that $f_{n,r}(t)$ is a prime power, the number-theoretic
conjectures and estimates we use are stated in terms of integers $t\geq 1$.
This is not a problem here, since we are not concerned with individual block
designs but with the existence or otherwise of infinite families of them. In
any case, the value $f_{n,r}(0)=\frac{r(r-1)}{2}-n$ is easily dealt with (see
Section 14).

##  8\. Verifying the Bunyakovsky conditions

The polynomials $f$ of interest in [2], and hence the main focus of this note,
are those of the form

(5) $f(t)=f_{n,r}(t)=8n^{2}t^{2}+2n(2r-1)t+\left(\frac{r(r-1)}{2}-n\right)$

for integers $n\geq 2$ and $r\geq 1$ with

(6) $r<4n\quad\hbox{and}\quad\frac{r(r-1)}{2}\equiv n+1\;\hbox{mod}\,(2n).$

Note that this last condition implies that $r\geq 3$.

######  Lemma 8.1.

If a polynomial $f=f_{n,r}$ of the form (5) satisfies (6), it also satisfies
Bunyakovsky’s conditions (a) and (c); it satisfies his condition (b) if and
only if $n$ is not a triangular number $a(a+1)/2$, $a\in{\mathbb{N}}$.

###### Proof.

Clearly $f$ satisfies condition (a) since $n\geq 1$. As a quadratic
polynomial, $f$ is reducible over $\mathbb{Z}$ if and only if its discriminant
$\Delta$ is a perfect square. Here

(7)
$\Delta=4n^{2}(2r-1)^{2}-32n^{2}\left(\frac{r(r-1)}{2}-n\right)=4n^{2}(8n+1),$

and this is a square if and only if $8n+1$ is. Simple algebra shows that the
solutions $n\in{\mathbb{N}}$ of $8n+1=l^{2}\;(l\in{\mathbb{Z}})$ are the
triangular numbers $n=1,3,6,10,\ldots$, those of the form $a(a+1)/2$ for some
$a=(l-1)/2\in{\mathbb{N}}$ (readers may enjoy finding a geometric ‘proof
without words’ for this), so $f$ will satisfy (b) if and only if $n$ does not
have this form.

We now check condition (c). If a prime $p$ divides $2n$ then $f$ reduces mod
$(p)$ to a constant polynomial; this takes the value $1$ since $r(r-1)/2\equiv
n+1$ mod $(2n)$, so $f$ is not identically zero mod $(p)$. If $p$ does not
divide $2n$ then $f$ reduces to a quadratic polynomial, with at most two
roots, so again it cannot be identically zero. ∎

In order to apply the Bateman–Horn Conjecture to the polynomials $f_{n,r}$, we
therefore restrict attention to those for which $n$ is not a triangular
number.

##  9\. Calculating $\omega_{f}(p)$ for $f_{n,r}$

Recall that $\omega_{f}(p)$, which appears in the infinite product (2), is the
number of roots of $f$ mod $(p)$ for each prime $p$. We saw in the proof of
Lemma 8.1 that $\omega_{f}(p)=0$ for any prime $p$ dividing $2n$. Primes $p$
dividing $8n+1$ (and thus not dividing $2n$) give $\Delta\equiv 0$ mod $(p)$
by (7), and hence $\omega_{f}(p)=1$ by the quadratic formula. Similarly, all
other primes $p$ give $\omega_{f}(p)=2$ or $0$ as $8n+1$ is or is not a
quadratic residue (non-zero square) mod $(p)$.

In general, given any prime $p$ and integer $q$, one can determine whether or
not $q$ is a quadratic residue mod $(p)$ by using the Legendre symbol

$\left(\frac{q}{p}\right)=\begin{cases}0\quad\;\hbox{if $q\equiv 0$
mod~{}$(p)$;}\\\ 1\quad\;\hbox{if $q$ is a quadratic residue mod~{}$(p)$;}\\\
-1\;\;\hbox{otherwise.}\end{cases}.$

(See [18, Chapter 7] for quadratic residues and the Legendre symbol.) Clearly

$\left(\frac{q}{p}\right)=\left(\frac{q^{\prime}}{p}\right)\quad\hbox{if
$q\equiv q^{\prime}$ mod~{}$(p)$,}$

and since the quadratic residues form a subgroup of index $2$ in the group of
units mod $(p)$ we have the multiplicative property, that

$\left(\frac{qq^{\prime}}{p}\right)=\left(\frac{q}{p}\right)\left(\frac{q^{\prime}}{p}\right)$

for all $q,q^{\prime}\in{\mathbb{Z}}$. Using these rules one can reduce the
calculation of the Legendre symbol to the cases where $q$ is an odd prime. In
such cases one can use the Law of Quadratic Reciprocity, that if $p$ and $q$
are distinct odd primes then

$\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)\quad\hbox{if $p$ or
$q\equiv 1$ mod~{}$(4)$,}$

while

$\left(\frac{q}{p}\right)=-\left(\frac{p}{q}\right)\quad\hbox{if $p\equiv
q\equiv-1$ mod~{}$(4)$.}$

We also have

$\left(\frac{2}{p}\right)=1\;\hbox{or}\;-1\quad\hbox{as}\quad p\equiv\pm
1\;\hbox{or}\;\pm 3\;{\rm mod}\,(8),$

and

$\left(\frac{-1}{p}\right)=1\;\hbox{or}\;-1\quad\hbox{as}\quad p\equiv
1\;\hbox{or}\;-1\;{\rm mod}\,(4).$

By iterating these rules one can reduce the values of $p$ and $q$ until they
are small enough to be dealt with by inspection.

We have seen that if $f=f_{n,r}$ then $\omega_{f}(p)=0$ for all primes $p$
dividing $2n$. For primes $p$ not dividing $2n$, by the definitions of the
function $\omega_{f}$ and the Legendre symbol, the quadratic formula gives
$\omega_{f}(p)=\left(\frac{\Delta}{p}\right)+1$. We will use this in the
following examples.

######  Example 9.1.

The smallest value of $n$ which is not a triangular number is $n=2$, giving
$8n+1=17$. Since $17\equiv 1$ mod $(4)$ we have

$\left(\frac{17}{p}\right)=\left(\frac{p}{17}\right)$

for any odd prime $p$. By squaring integers one sees that the quadratic
residues mod $(17)$ are $\pm 1,\pm 2,\pm 4$ and $\pm 8$ (in fact, under
multiplication mod $(17)$ they form a cyclic group of order $8$, generated by
$2$). Thus, if $f=f_{2,r}$ for some $r$ then $\omega_{f}(p)=2$ for odd primes
$p\equiv\pm 1,\pm 2,\pm 4$ or $\pm 8$ mod $(17)$, while $\omega_{f}(p)=0$ for
primes $p\equiv\pm 3,\pm 5,\pm 6$ or $\pm 7$ mod $(17)$. For the remaining
primes $p$ we have $\omega_{f}(2)=0$ and $\omega_{f}(17)=1$.

######  Example 9.2.

The second smallest value of $n$ which is not a triangular number is $n=4$,
giving $8n+1=33$. In this case multiplicativity and quadratic reciprocity give

$\left(\frac{33}{p}\right)=\left(\frac{3}{p}\right)\left(\frac{11}{p}\right)=\left(\frac{p}{3}\right)\left(\frac{p}{11}\right)$

for all odd primes $p\neq 3,11$, since $3\equiv 11$ mod $(4)$ so that any
minus signs cancel. Now the quadratic residues mod $(3)$ and mod $(11)$ are
$1$ and $1,3,4,5,9$ respectively. The primes $p$ for which $33$ is a quadratic
residue mod $(p)$ are those which are both residues or both non-residues mod
$(3)$ and mod $(11)$, so solving the relevant pairs of simultaneous
congruences gives the classes $\pm 1,\pm 2,\pm 4,\pm 8,\pm 16$ mod $(33)$
(forming a cyclic group generated by $2$). If $f=f_{4,r}$ for some $r$ then
for odd primes $p$ in these classes we have $\omega_{f}(p)=2$, whereas for
$p\equiv\pm 5,\pm 7,\pm 10,\pm 13,\pm 14$ mod $(33)$ we have
$\omega_{f}(p)=0$. For the remaining primes $p$ we have $\omega_{f}(2)=0$ and
$\omega_{f}(3)=\omega_{f}(11)=1$.

Notice that the classes $\pm 3,\pm 6,\pm 9,\pm 12,\pm 15$ and $\pm 11$ are not
present in the above two lists: they are not coprime with $33$ and therefore
cannot be residues of a prime $p>11$ modulo $33$.

######  Example 9.3.

The next case $n=5$ is similar to Example 9.1 since $8n+1=41$ is prime. We
find that $\omega_{f}(2)=\omega_{f}(5)=0$ and $\omega_{f}(41)=1$, while for
other primes $p$ we have $\omega_{f}(p)=2$ or $0$ as $p$ is or is not a
quadratic residue mod $(41)$. These are $\pm 1,\pm 2,\pm 4,\pm 5,\pm 8,\pm
9,\pm 10,\pm 16,\pm 18,\pm 20$.

For other permitted values of $n$ the process is similar: thus for $n=7$, $8$
and $9$ we have $8n+1=57=3\cdot 19$, $65=5\cdot 13$ and $73$ which is prime.
However, in some cases the process can be lengthier, depending on the
factorisation of $8n+1$. We give just one more typical example.

######  Example 9.4.

If $n=13$ then $8n+1=105=3\cdot 5\cdot 7$. Since $3\equiv 7\equiv-1$ mod $(4)$
while $5\equiv 1$ mod $(4)$ we have

$\left(\frac{105}{p}\right)=\left(\frac{3}{p}\right)\left(\frac{5}{p}\right)\left(\frac{7}{p}\right)=\left(\frac{p}{3}\right)\left(\frac{p}{5}\right)\left(\frac{p}{7}\right)$

for all primes $p\geq 11$, so for such $p$ we have $\omega_{f}(p)=0$ or $2$ as
$p$ is a quadratic residue modulo an even or odd number of the primes $3,5$
and $7$. Since the quadratic residues modulo these primes are generated by
$1$, $-1$ and $2$ respectively, this is easily determined in terms of
congruences mod $(105)$. (For some primes $p$, short-cuts are possible: for
instance $105\equiv-1$ mod $(53)$, so
$\left(\frac{105}{53}\right)=\left(\frac{-1}{53}\right)=1$, and similarly
$\left(\frac{105}{107}\right)=\left(\frac{-1}{107}\right)\left(\frac{2}{107}\right)=(-1)^{2}=1$.)
For $p=3$, $5$ or $7$ we have $\omega_{f}(p)=1$, while
$\omega_{f}(2)=\omega_{f}(13)=0$.

Since the values of $\omega_{f}(p)$ depend only on a few simple congruences
for $p$, it is straightforward to program Maple to determine the factors in
the infinite product (2) and hence to evaluate $C$. Note also that this part
of the process depends only on $n$, and not on $r$, so that polynomials
$f_{n,r}$ with the same parameter $n$ can be dealt with simultaneously.

##  10\. Evaluating the estimates

Since the factors in (2) approach $1$ quite slowly as $p\to\infty$,
convergence of this infinite product is rather slow, and one needs to multiply
many terms in order to obtain good approximations for $C$. In our computations
we used all the primes $p\leq 10^{8}$.

Maple calculates the definite integral in (1) by numerical quadrature. We
found that running times were less than a second. Bateman and Horn simplified
this part of the process by replacing $\ln(f(t))$ with $\deg(f)\ln(t)$ in (1),
thus ignoring the leading coefficient of $f$ together with all non-leading
terms. No doubt, working in the early 1960s without resources such as Maple,
they found that this shortcut was essential, especially in cases involving
more than one polynomial. Li’s recent improvement [22], using $\ln(f(t))$,
certainly leads to more accurate estimates. In fact, the non-leading terms
have remarkably little effect on the value of the integral (so again, $r$ is
almost irrelevant), whereas most of the extra accuracy comes from including
the leading coefficient. For instance, the estimates $E(10^{8})$ for the
polynomials $f_{2,3}(t)=32t^{2}+20t+1$ and $f_{2,6}(t)=32t^{2}+44t+13$, given
in the next section, differ by only $0.29$.

For each polynomial $f$ we used Maple to find the actual number $Q(x)$ of
prime values of $f(t)$ for $t\leq x=10^{8}$. Since, for example,
$f_{5,r}(10^{8})\approx 2\cdot 10^{18}$, this was the most time-consuming part
of our computations, with running times of about two hours on a modest laptop.
Maple uses the Rabin–Miller primality test, which is probabilistic rather than
deterministic. If an integer is prime, the test will always declare it to be
prime. If an integer is composite, the test may incorrectly declare it to be
prime, but the probability of this happening is so small that in forty years
of use of the test, no such incident has ever been reported. In our case, we
found so many prime values of the polynomials $f$ which we considered that,
even if we have been very unlucky and a few of them are actually composite,
this will have a negligible effect on our evidence.

##  11\. The estimates and their accuracy

###  11.1. The case $n=2$.

The smallest allowed value for the parameter $n$ is $2$, so condition (6)
implies that $r=3$ or $6$. In either case, evaluating $\omega_{f}(p)$ as in
Example 9.1, and taking the product in (2) over all primes $p\leq 10^{8}$, we
found that $C=4.721240276\ldots$. Putting $r=3$ gives

$f(t)=f_{2,3}(t)=32t^{2}+20t+1.$

Taking $x=10^{i}$ for $i=3,4,\ldots,8$ we found the estimates $E(x)$ for the
values of $Q(x)$ shown in Table 1. The final column, showing the relative
error, reveals the accuracy of these estimates.

$x$ | $Q(x)$ | $E(x)$ | relative error
---|---|---|---
$10^{3}$ | 326 | $314.49$ | $-3.53\%$
$10^{4}$ | 2421 | $2404.86$ | $-0.67\%$
$10^{5}$ | 19 394 | $19\,438.26$ | $0.23\%$
$10^{6}$ | 162 877 | $163\,182.75$ | $0.19\%$
$10^{7}$ | 1 405 448 | $1\,406\,630.14$ | $0.084\%$
$10^{8}$ | 12 357 532 | $12\,362\,961.06$ | $0.044\%$
Table 1. Numbers $Q(x)$ and estimates $E(x)$ for $f_{2,3}$.

###  11.2. The cases with $n\leq 9$

$(n,r)$ | $f_{(n,r)}(t)$ | $C(f)$ | $Q(10^{8})$ | $E(10^{8})$ | relative error
---|---|---|---|---|---
$(2,3)$ | $32t^{2}+20t+1$ | $4.72124$ | $12\,357\,532$ | $12\,362\,961.06$ | $0.0439\%$
$(2,6)$ | $32t^{2}+44t+13$ |  | $12\,363\,849$ | $12\,362\,960.77$ | $-0.0072\%$
$(4,7)$ | $128t^{2}+104t+17$ | $3.20688$ | $8\,100\,174$ | $8\,102\,333.64$ | $0.0267\%$
$(4,10)$ | $128t^{2}+152t+41$ |  | $8\,104\,531$ | $8\,102\,333.57$ | $-0.0271\%$
$(5,4)$ | $200t^{2}+70t+1$ | $5.62398$ | $14\,052\,016$ | $14\,050\,339.22$ | $-0.012\%$
$(5,9)$ | $200t^{2}+170t+31$ |  | $14\,049\,951$ | $14\,050\,339.05$ | $0.003\%$
$(5,12)$ | $200t^{2}+230t+61$ |  | $14\,057\,558$ | $14\,050\,338.95$ | $-0.051\%$
$(5,17)$ | $200t^{2}+330t+131$ |  | $14\,049\,868$ | $14\,050\,338.79$ | $0.003\%$
$(7,9)$ | $392t^{2}+238t+29$ | $3.82010$ | $9\,381\,546$ | $9\,385\,428.26$ | $0.0415\%$
$(7,13)$ | $392t^{2}+350t+71$ |  | $9\,387\,937$ | $9\,385\,428.21$ | $-0.0267\%$
$(7,16)$ | $392t^{2}+434t+113$ |  | $9\,385\,853$ | $9\,385\,428.17$ | $-0.0045\%$
$(7,20)$ | $392t^{2}+546t+183$ |  | $9\,387\,135$ | $9\,385\,428.11$ | $-0.0182\%$
$(8,15)$ | $512t^{2}+464t+97$ | $3.22754$ | $7\,879\,429$ | $7\,877\,750.61$ | $-0.0213\%$
$(8,18)$ | $512t^{2}+560t+145$ |  | $7\,879\,013$ | $7\,877\,750.57$ | $-0.0160\%$
$(9,5)$ | $648t^{2}+162t+1$ | $5.41032$ | $13\,129\,138$ | $13\,129\,743.85$ | $0.0046\%$
$(9,8)$ | $648t^{2}+270t+19$ |  | $13\,127\,661$ | $13\,129\,739.69$ | $0.0158\%$
$(9,17)$ | $648t^{2}+594t+127$ |  | $13\,129\,080$ | $13\,129\,739.55$ | $0.0050\%$
$(9,20)$ | $648t^{2}+702t+181$ |  | $13\,130\,890$ | $13\,129\,743.63$ | $-0.0087\%$
$(9,29)$ | $648t^{2}+1026t+397$ |  | $13\,128\,036$ | $13\,129\,743.50$ | $0.0130\%$
$(9,32)$ | $648t^{2}+1134t+487$ |  | $13\,128\,979$ | $13\,129\,743.46$ | $0.0058\%$
Table 2. Complete list of irreducible polynomials $f_{n,r}$ defined in (5) and
satisfying conditions (6), for $n\leq 9$. The constants $C(f)$ are computed
over primes $p\leq 10^{8}$.

The process for the remaining polynomials $f_{n,r}$ with non-triangular
numbers $n\leq 9$ was similar, with $x=10^{8}$ in all cases. Table 2
summarises the results.

######  Remark 11.1.

The greater the leading coefficient of a polynomial, the more significant is
Li’s improvement in [22] as compared with the initial Bateman–Horn formula in
[4]. For example, in the case of $f(t)=f_{9,5}(t)=648t^{2}+162t+1$, we have
two corresponding estimates

$E_{\rm Li}=C\cdot\int_{2}^{10^{8}}\frac{dt}{\ln(f(t))}\quad\hbox{and}\quad
E_{\rm BH}=\frac{C}{2}\cdot\int_{2}^{10^{8}}\frac{dt}{\ln(t)}$

for $x=10^{8}$, with relative errors $0.0046\%$ and $18.7\%$ respectively.

This does not contradict the fact that the two estimates are asymptotically
equivalent. Indeed, the relative error of $E_{\rm BH}$ steadily decreases to
approximately $2\%$ when the upper limit $x$ of the integration approaches
$10^{70}$. (Of course, we did not count the true number $Q(x)$ of prime values
of this polynomial: instead, we took $E_{\rm Li}(x)$ as if it were the true
value of $Q(x)$.)

##  12\. Prime power values

We restricted our estimates to prime values of the polynomials $f_{n,r}$,
since the Bunyakovsky and Bateman–Horn Conjectures have nothing to say about
composite values. However, since the constructions of block designs in [2]
apply to values which are prime powers, not just primes, we extended our
computer searches to proper prime power values of some of these polynomials,
for $t\leq x=10^{7}$.

As predicted in Section 2, we found very few proper prime power values, in
comparison with the abundance of prime values. The values we found for $n\leq
9$ and $t\leq 10^{7}$ are shown in Table 3. We observe that there is only one
cube: all the other prime powers are squares. The polynomials $f_{n,r}$ for
the following pairs $(n,r)$ with non-triangular parameters $n\leq 9$ gave no
proper prime power values for $t\leq 10^{7}$, so they have been omitted from
the table:

$(2,6),\;(4,7),\;(4,10),\;(5,9),\;(5,12),\;(5,17),\;(7,9),\;(7,13),\;(7,16),\;(7,20),$
$(8,15),\;(8,18),\;(9,8),\;(9,20),\;(9,32).$

$(n,r)$ | polynomial $f_{n,r}$ | $t\leq 10^{7}$ | $f_{n,r}(t)$ | power
---|---|---|---|---
$(2,3)$ | $32t^{2}+20t+1$ | 2 | 169 | $13^{2}$
|  | 8 | 2 209 | $47^{2}$
|  | 78 | 196 249 | $443^{2}$
|  | 282 | 2 550 409 | $1\,597^{2}$
|  | 9 590 | 2 943 171 001 | $54\,251^{2}$
|  | 23 666 | 17 923 019 113 | $2\,617^{3}$
|  | 90 372 | 261 348 955 729 | $511\,223^{2}$
|  | $3\,069\,998$ | $301\,596\,468\,440\,089$ | $17\,366\,533^{2}$
$(5,4)$ | $200t^{2}+70t+1$ | 4 | 3 481 | $59^{2}$
|  | 2 044 | 835 730 281 | $28\,909^{2}$
|  | 4 816 | 4 639 108 321 | $68\,111^{2}$
|  | 163 608 | 5 353 526 985 361 | $2\,313\,769^{2}$
$(9,5)$ | $648t^{2}+162t+1$ | 3 220 | 6 719 244 841 | $81\,971^{2}$
$(9,17)$ | $648t^{2}+594t+127$ | $1$ | $1\,369$ | $37^{2}$
|  | $49$ | $1\,585\,081$ | $1\,259^{2}$
$(9,29)$ | $648t^{2}+1\,026t+397$ | 2 | 5 041 | $71^{2}$
Table 3. Proper prime power values for irreducible polynomials $f_{n,r}$ with
$n\leq 9$, $t\leq 10^{7}$

##  13\. Prime power values of reducible polynomials

A reducible polynomial $f(t)=g(t)h(t)\in{\mathbb{Z}}[t]$ can take only
finitely many prime values (with $g(t)$ or $h(t)$ equal to $\pm 1$), but could
it take infinitely many prime power values? One way it might do so is if $g=h$
and this polynomial takes infinitely many prime values: Dirichlet’s Theorem
shows that this can happen with $\deg g=1$, and the Bunyakovsky Conjecture
suggests that it can happen with $\deg g>1$. More generally, if $g$ is
irreducible and takes infinitely many prime values $p$, then any power
$f=g^{e}$ of $g$ takes infinitely many prime power values $p^{e}$. But what
happens if $f$ has two or more distinct irreducible factors?

######  Theorem 13.1.

If $f$ is a polynomial in ${\mathbb{Z}}[t]$ with at least two different
irreducible factors, then $f(t)$ is a prime power for only finitely many
$t\in{\mathbb{Z}}$.

###### Proof.

We first deal with a simple special case, and with $t\geq 0$. Suppose that
$f=gh$ for distinct factors $g(t)=a_{k}t^{k}+\cdots$ and
$h(t)=b_{k}t^{k}+\cdots$ in ${\mathbb{Z}}[t]$ of the same degree $k\geq 1$. If
there is some $t\in{\mathbb{N}}$ with $f(t)=p^{e}$ for a prime $p$ and integer
$e\geq 1$ then $g(t)=\pm p^{i}$ and $h(t)=\pm p^{j}$ for some integers
$i,j\geq 0$ with $i+j=e$. If $i\geq j$ then

$\frac{g(t)}{h(t)}=p^{i-j}\in{\mathbb{Z}}.$

However, for all sufficiently large $t\in{\mathbb{R}}$ we have

$\frac{g(t)}{h(t)}=\frac{a_{k}t^{k}+\cdots}{b_{k}t^{k}+\cdots}\to\frac{a_{k}}{b_{k}}\quad\hbox{strictly
monotonically as}\;\;t\to+\infty,$

so if there are infinitely many such $t\in{\mathbb{N}}$ with $i\geq j$ we have
a sequence of integers $p^{i-j}$ converging strictly monotonically to
$a_{k}/b_{k}$, which is impossible. A similar argument, with the factors $g$
and $h$ transposed, shows that there can be only finitely many such
$t\in{\mathbb{N}}$ with $i<j$, so $f(t)$ is a prime power for only finitely
many $t\in{\mathbb{N}}$.

We can now deal with the general case, where $f$ is reducible and not a power
of a single irreducible polynomial. This allows us to factorise $f$ in
${\mathbb{Z}}[t]$ as $f=gh$ where $g$ and $h$ have different irreducible
factors. If $\deg g\neq\deg h$ we can replace $f$ with

$f^{*}=g^{*}h^{*}\quad\hbox{where}\quad g^{*}=g^{\deg h}\quad\hbox{and}\quad
h^{*}=h^{\deg g},$

so that $f^{*}$ takes prime power values at the same integers $t$ as $f$ does.
Since $g^{*}$ and $h^{*}$ are distinct but have the same degree, we can apply
the preceding argument to show that $f^{*}$ takes prime power values at only
finitely many $t\in{\mathbb{N}}$, and hence the same applies to $f$. Finally,
we can extend this result to all $t\in{\mathbb{Z}}$ either directly as above,
using the fact that $g(t)/h(t)$ has similar limiting behaviour when
$t\to-\infty$, or by applying the above argument for $t>0$ to $f(-t)$, which
factorises in the same way as $f(t)$. ∎

In particular, let $f=f_{n,r}$ in a case where this polynomial is reducible,
or equivalently $n$ is a triangular number $a(a+1)/2$ and $\Delta$ is a non-
zero square $4n^{2}(8n+1)=4n^{2}(2a+1)^{2}$. Then $f$ factorises in
${\mathbb{Z}}[t]$ as

$f(t)=g(t)h(t)=\frac{1}{2}(4nt+r+a)(4nt+r-a-1),$

where the first or second displayed linear polynomial has both of its
coefficients even as $r\equiv a$ mod $(2)$ or not, so that it absorbs the
factor $\frac{1}{2}$. In either case, the resulting linear factors $g$ and $h$
of $f$ in ${\mathbb{Z}}[t]$ are distinct and irreducible, so Theorem 13.1
implies that $f(t)$ is a prime power for only finitely many
$t\in{\mathbb{Z}}$.

######  Proposition 13.2.

If $f_{n,r}$ is reducible and $n>1$ then $f_{n,r}(t)$ is not a prime power for
any integer $t\geq 1$.

###### Proof.

Suppose that $f:=f_{n,r}$ is reducible and $n>1$, so $n=a(a+1)/2$ for some
integer $a\geq 2$ by Lemma 8.1, and that $f(t)=p^{e}$ for some prime $p$ and
integers $e,t\geq 1$.

Case 1 If $r\equiv a$ mod $(2)$ then $f=gh$ where

$g(t)=2nt+\frac{r+a}{2}\quad\hbox{and}\quad h(t)=4nt+r-a-1.$

Since $t\geq 1$ we have $g(t),h(t)>1$ so $g(t)=p^{i}$ and $h(t)=p^{j}$ for
integers $i,j\geq 1$ with $i+j=e$. If $i<j$ then

$\frac{h(t)}{g(t)}=p^{j-i}\geq p\geq 2,$

giving $-a-1\geq a$, which is impossible since $a\geq 1$. Thus $i\geq j$, so
$g(t)\geq h(t)$, leading to

$t\leq\frac{3a-r+2}{4n}\leq\frac{3a+1}{2a(a+1)}<1$

(since $r\geq 1$ and $a\geq 2$), against our hypothesis.

Case 2 If $r\not\equiv a$ mod $(2)$ then $f=gh$ where

$g(t)=4nt+r+a\quad\hbox{and}\quad h(t)=2nt+\frac{r-a-1}{2}.$

As before we have $g(t)=p^{i}$ and $h(t)=p^{j}$ for integers $i,j\geq 1$. If
$i\leq j$ then $g(t)\leq h(t)$, leading to

$2nt\leq\frac{r-a-1}{2}-(r+a)<0,$

which is impossible. Thus $i>j$, so

$\frac{g(t)}{h(t)}=p^{i-j}\geq p.$

If $p^{i-j}=2$ then $g(t)=2h(t)$, giving $a=-a-1$, which is impossible. Hence
$p^{i-j}\geq 3$, so $g(t)\geq 3h(t)$, leading to

$t\leq\frac{a-r+3}{4n}\leq\frac{a}{4n}=\frac{1}{2(a+1)}<1,$

again contradicting our hypothesis. ∎

######  Remark 13.3.

Although Theorem 13.1 applies to all $t\in{\mathbb{Z}}$, Proposition 13.2
applies only to integers $t\geq 0$ and cannot be extended to the case $t<0$.
For example, the polynomial

$f(t)=f_{3,5}(t)=72t^{2}+54t+7=(12t+7)(6t+1),$

satisfies $f(-1)=5^{2}$, with $g(-1)=h(-1)=-5$. Of course, negative values of
$t$ are not relevant to the 2-designs considered in this paper.

The condition $n>1$ is required in Proposition 13.2, since the polynomial

$f(t)=f_{1,1}(t)=8t^{2}+2t-1=(2t+1)(4t-1)$

satisfies $f(1)=3^{2}$. The block designs $\mathcal{D}$ considered here all
satisfy this condition.

##  14\. Values at $t=0$

Proposition 13.2 leaves open the possibility, which is relevant to 2-designs,
that

$f(0)=f_{n,r}(0)=\frac{r(r-1)}{2}-n$

could be a prime power. Prime values $f_{n,r}(0)$ seem to arise quite
frequently when $f_{n,r}$ is irreducible: for example, of the twenty
polynomials in Table 2, sixteen have prime values at $t=0$, three have the
value $1$, and $f_{8,18}$ has the value $145$. However, the situation is
rather different for reducible polynomials $f_{n,r}$, those for which $n$ is a
triangular number $a(a+1)/2$.

######  Proposition 14.1.

Let $f_{n,r}$ be reducible, and satisfy (5) and (6). Then $f_{n,r}(0)$ is a
prime power $p^{e}$, $e\geq 1$, if and only if $p$ is odd and one of the
following occurs:

  * a)

$e=2i$ is even, with $n=(p^{e}-1)/8>1$, $a=(p^{i}-1)/2$ and $r=(3p^{i}+1)/2$,
or

  * b)

$p^{e}=7$, with $n=3$, $a=2$ and $r=5$ $($as in Remark 13.3).

Note that by (a) every even power $p^{e}>9$ of an odd prime $p$ can be
realised as a value $f_{n,r}(0)$ of a reducible polynomial $f_{n,r}$.

######  Example 14.2.

One can realise $5^{2}$ as a value by taking $n=3$, $a=2$ and $r=8$. This
gives

$f(t)=f_{3,8}(t)=72t^{2}+90t+25=(6t+5)(12t+5)$

with $f(0)=5^{2}$. Similarly, one can realise $7^{2}$ by taking $n=6$, $a=3$
and $r=11$, so that

$f(t)=f_{6,11}(t)=288t^{2}+252t+49=(12t+7)(24t+7)$

with $f(0)=7^{2}$. Taking $n=(13^{4}-1)/8=3\,570$ and $r=(3\cdot
13^{2}+1)/2=254$ we get

$f(t)=f_{n,r}(t)=101\,959\,200\,t^{2}+3\,619\,980\,t+28\,561=(7\,140t+169)(14\,280t+169)$

with $f(0)=28\,561=13^{4}$.

Proof of Proposition 14.1. If we put $t=0$ in Case (1) of the proof of
Proposition 13.2, where $r\equiv a$ mod $(2)$, we have

$\frac{r+a}{2}=p^{i}\quad\hbox{and}\quad r-a-1=p^{j}$

for integers $i,j\geq 0$ with $i+j=e\geq 1$ and $i\geq j$. Solving these
simultaneous equations gives

$r=p^{i}+\frac{p^{j}+1}{2}\quad\hbox{and}\quad a=p^{i}-\frac{p^{j}+1}{2},$

so that

$n=\frac{a(a+1)}{2}=\frac{1}{8}\left((2p^{i}-p^{j})^{2}-1\right).$

(Recall that $f_{n,r}$ is reducible if and only if $8n+1$ is a perfect
square.) Here we require $p^{j}$ to be odd, so that $r\equiv a$ mod $(2)$;
however, we reject solutions with $p=2$ and $j=0$ since they give $c=2^{i}$
and $r(r-1)/2\not\equiv n+1$ mod $(2n)$, contradicting condition (6), so $p$
must be an odd prime.

The condition that $r(r-1)/2\equiv n+1$ mod $(2n)$ also excludes many
solutions when $p$ is odd. We have

$\frac{r(r-1)}{2}-n-1=p^{i+j}-1\quad\hbox{and}\quad
2n=\frac{((2p^{i}-p^{j})^{2}-1}{4},$

so if $i>j$ then

$0<\frac{r(r-1)}{2}-n-1<2n$

and hence $r(r-1)/2\not\equiv n+1$ mod $(2n)$. However, if we take $i=j$ then

$r=\frac{3p^{i}+1}{2},\quad a=\frac{p^{i}-1}{2}\quad\hbox{and}\quad
n=\frac{p^{2i}-1}{8},$

so that $r<4n$ provided $p^{i}>3$, and

$\frac{r(r-1)}{2}-n-1=p^{2i}-1=8n\equiv 0\;{\rm mod}\,(2n)$

as required. Thus every even power $p^{e}=p^{2i}>9$ of an odd prime $p$ is the
value of some reducible polynomial $f_{n,r}$ at $t=0$, giving conclusion (a).

A similar argument applies in Case (2) of the proof of Proposition 13.2, where
$r\not\equiv a$ mod $(2)$. We now have

$r+a=p^{i}\quad\hbox{and}\quad\frac{r-a-1}{2}=p^{j},$

with $i>j$, so that

$r=\frac{p^{i}+1}{2}+p^{j}\quad\hbox{and}\quad a=\frac{p^{i}-1}{2}-p^{j},$

giving

$n=\frac{a(a+1)}{2}=\frac{1}{8}\left((p^{i}-2p^{j})^{2}-1\right).$

In this case

$\frac{r(r-1)}{2}-n-1=p^{i+j}-1\quad\hbox{and}\quad
2n=\frac{((p^{i}-2p^{j})^{2}-1}{4}.$

We need

$p^{i+j}-1=\frac{r(r-1)}{2}-n-1\geq 2n=\frac{p^{2i}-1}{4}-p^{i+j}+p^{2j}$

so that

$2p^{i+j}\geq\frac{p^{2i}+3}{4}+p^{2j}>\frac{p^{2i}}{4}$

and hence $p^{i-j}\leq 8$. Since $i>j$ and $p\geq 3$ this implies that $i-j=1$
and $p=3,5$ or $7$. Thus only odd powers $p^{e}$ of these three primes can
arise in Case 2.

Putting $i=j+1$ gives

$\frac{r(r-1)}{2}-n-1=p^{2j+1}-1\quad\hbox{and}\quad
2n=\frac{(p^{j+1}-2p^{j})^{2}-1}{4}=\frac{(p-2)^{2}p^{2j}-1}{4}.$

Now $2n$ divides $\frac{r(r-1)}{2}-n-1$, so multiplying by $4$ shows that

$8n=(p-2)^{2}p^{2j}-1\quad\hbox{divides}\quad
4\left(\frac{r(r-1)}{2}-n-1\right)=4(p^{2j+1}-1)$

Defining $q:=p^{2j}$, we see that $(p-2)^{2}q-1$ divides $4(pq-1)$. We now
apply this with $p=3$, $5$ and $7$ in turn.

If $p=3$ then $q-1$ divides $12q-4=12(q-1)+8$, so $q-1$ divides $8$, giving
$q=1$ or $9$. If $q=1$ then $j=0$, giving $r=3$, $a=0$ and $n=0$, whereas we
need $n>1$. If $q=9$ then $j=1$, giving $r=8$, $a=1$ and $n=1$, again too
small. Thus $p\neq 3$.

If $p=5$ then $9q-1$ divides $20q-4=2(9q-1)+2(q-1)$ and hence $9q-1$ divides
$2(q-1)$ giving $q=1$. Then $j=0$, so $r=4$, $a=1$ and $n=1$, whereas we need
$n>1$. Thus $p\neq 5$.

If $p=7$ then $25q-1$ divides $28q-4=25q-1+3(q-1)$ and hence $25q-1$ divides
$3(q-1)$ giving $q=1$. Then $j=0$, so $r=5$, $a=2$ and $n=3$, with $r<4n$ and
$r(r-1)/2-n-1=6\equiv 0$ mod $(2n)$; this gives the polynomial

$f(t)=f_{3,5}(t)=72t^{2}+54t+7=(12t+7)(6t+1)$

in conclusion (b), with $f(0)=7$. $\Box$

##  15\. Conclusions

We have found large numbers of prime values of those polynomials $f_{n,r}$
appearing in [2] for which $n$ is not a triangular number. The numbers found
agree closely with the estimates for them provided by Li’s recent version of
the Bateman–Horn Conjecture. While this does not prove the conjecture in [2]
that these polynomials take infinitely many prime values, and thus give
infinite families of block designs, it provides strong evidence for this, and
it also adds extra support for the validity of the Bunyakovsky and
Bateman–Horn Conjectures.

##  16\. Acknowledgements

We are grateful to Yuri Bilu, to Cheryl Praeger and to Weixiong Li for many
useful comments. Alexander Zvonkin was partially supported by the ANR project
Combiné (ANR-19-CE48-0011).

## References

  * [1] S. L. Aletheia-Zomlefer, L. Fukshansky and S. R. Garcia, The Bateman–Horn conjecture: heuristics, history, and applications, Expo. Math. 38 (2020), 430–479. Also available at arXiv-math[NT]:1807.08899v4.
  * [2] C. Amarra, A. Devillers and C. E. Praeger, Delandsheer–Doyen parameters for block-transitive point-imprimitive block designs, arXiv-math[CO]:2009.00282.
  * [3] W. D. Banks, F. Pappalardi and I. E. Shparlinski On group structures realized by elliptic curves over arbitrary finite fields, Exp. Math. 21 (2012), 11–25.
  * [4] P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 220–228.
  * [5] Z. I. Borevich and I. R. Shafarevich, Number Theory, Academic Press, New York and London, 1966.
  * [6] V. Bouniakowsky, Sur les diviseurs numériques invariables des fonctions rationnelles entières, Mém. Acad. Sci. St. Péteresbourg, $6^{\rm e}$ série, vol. VI (1857), 305–329.111Numerous publications give the following wrong title for Bunyakovsky’s paper: “Nouveaux théorèmes relatifs à la distinction des nombres premiers et à la décomposition des entiers en facteurs”. According to the French Wikipedia (see [8]), an article with this title does indeed exist, but it was published in 1840 and not in 1857, and it does not discuss the conjecture in question. The reader may also consult the original paper reproduced in the Google archive. Available at: https://books.google.fr/books?hl=fr&id=wXIhAQAAMAAJ&pg=PA305#v=onepage&q&f=false.
  * [7] J. Boxall and D. Gruenewald, Heuristics on pairing-friendly abelian varieties, LMS J. Comput. Math. 18 (2015), 419–443.
  * [8] Bunyakovsky conjecture, Wikipedia, https://en.wikipedia.org/wiki/Bunyakovsky_conjecture. Conjecture de Bouniakovsky, Wikipédia, https://fr.wikipedia.org/wiki/Conjecture_de_Bouniakovski.
  * [9] H. Cohen, High-precision computation of Hardy–Littlewood constants, Available at https://oeis.org/A221712/a221712.pdf.
  * [10] J. D. Cook, Distribution of prime powers, John D. Cook’s blog, https://www.johndcook.com/blog/2018/09/03/counting-prime-powers.
  * [11] S. Covanov and E. Thomé, Fast integer multiplication using generalized Fermat primes, Math. Comp. 8 (2019), 1449–1477.
  * [12] C. David and E. Smith, A Cohen–Lenstra phenomenon for elliptic curves, J. London Math. Soc. (2) 89 (2014), 24–44.
  * [13] A. Delandtsheer and J. Doyen, Most block-transitive $t$-designs are point-primitive, Geom. Dedicata 29 (1989), 307–310.
  * [14] D. Ellis, G. Kalai and B. Narayanan, On symmetric intersecting families, European J. Combin. 86 (2020), 103094.
  * [15] L. Euler, letter to Goldbach, 28th October 1752 (letter CXLIX), available at http://eulerarchive.maa.org/correspondence/letters/OO0877.pdf. See also De numeris primis valde magnis, Novi Commentarii academiae scientiarum Petropolitanae 9, 99–153 (1760); reprinted in Commentat. arith. 1, 356–378, 1849, and in Opera Omnia: Ser. 1, vol. 3, 1–45.
  * [16] G. H. Hardy and J. E. Littlewood, Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes, Acta Math. 114 (1923), 215–273.
  * [17] M. J. Jacobson, Jr., and H. G. Williams, New quadratic polynomials with high densities of prime values, Math. Comp. 72 (2002), no. 241, 499–519.
  * [18] G. A. Jones and J. M. Jones, Elementary Number Theory, Springer, 1998.
  * [19] G. A. Jones and A. K. Zvonkin, Klein’s ten planar dessins of degree 11, and beyond, https://arxiv.org/pdf/2104.12015.pdf. To appear.
  * [20] G. A. Jones and A. K. Zvonkin, Projective primes and the Bateman–Horn Conjecture, https://arxiv.org/pdf/2106.00346.pdf.
  * [21] D. Kim, Nonexistence of perfect 2-error-correcting Lee codes in certain dimensions, European J. Combin. 63 (2017), 1–5.
  * [22] W. Li, A note on the Bateman–Horn conjecture, J. Number Theory 208 (2020), 390–399. Also available at https://arxiv.org/pdf/1906.03370.pdf.
  * [23] I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers (5th ed.), Wiley, New York, 1991.
  * [24] The Online Encyclopedia of Integer Sequences, Entry A006880, https://oeis.org/A006880.
  * [25] I. Rivin, Some experiments on Bateman–Horn, 2015, https://arxiv.org/pdf/1508.07821.
  * [26] T. Scholl, Isolated elliptic curves and the MOV attack, J. Math. Cryptol. 11 (2017), 131–146.
  * [27] T. Scholl, Super-isolated elliptic curves and abelian surfaces in cryptography, Exp. Math. 28 (2019), 385–397.
  * [28] M. Sha, Heuristics of the Cocks–Pinch method, Adv. Math. Commun. 8 (2014), 103–118.
  * [29] D. Shanks and M. Lal, Bateman’s constant reconsidered and the distribution of cubic residues, Math. Comp. 26 (1972), no. 117, 265–285.


* [53] B. C. Allanach, J. Davighi, and S. Melville, “An Anomaly-free Atlas: charting the space of flavour-dependent gauged $U(1)$ extensions of the Standard Model,” JHEP 02 (2019) 082, arXiv:1812.04602 [hep-ph]. [Erratum: JHEP 08, 064 (2019)].
  * [54] D. B. Costa, B. A. Dobrescu, and P. J. Fox, “General Solution to the U(1) Anomaly Equations,” Phys. Rev. Lett. 123 no. 15, (2019) 151601, arXiv:1905.13729 [hep-th].
  * [55] M. B. Green and J. H. Schwarz, “Anomaly Cancellation in Supersymmetric D=10 Gauge Theory and Superstring Theory,” Phys. Lett. B 149 (1984) 117–122.
  * [56] R. Barbier et al., “R-parity violating supersymmetry,” Phys. Rept. 420 (2005) 1–202, arXiv:hep-ph/0406039.
  * [57] J. M. Arnold, B. Fornal, and M. B. Wise, “Phenomenology of scalar leptoquarks,” Phys. Rev. D 88 (2013) 035009, arXiv:1304.6119 [hep-ph].
  * [58] W. Altmannshofer, J. Davighi, and M. Nardecchia, “Gauging the accidental symmetries of the standard model, and implications for the flavor anomalies,” Phys. Rev. D 101 no. 1, (2020) 015004, arXiv:1909.02021 [hep-ph].
  * [59] G. Buchalla and A. J. Buras, “The rare decays $K^{+}\to\pi^{+}\nu\bar{\nu}$ and $K_{L}\to\mu^{+}\mu^{-}$ beyond leading logarithms,” Nucl. Phys. B 412 (1994) 106–142, arXiv:hep-ph/9308272.
  * [60] M. Misiak and J. Urban, “QCD corrections to FCNC decays mediated by Z penguins and W boxes,” Phys. Lett. B 451 (1999) 161–169, arXiv:hep-ph/9901278.
  * [61] G. Buchalla and A. J. Buras, “The rare decays $K\to\pi\nu\bar{\nu}$, $B\to X\nu\bar{\nu}$ and $B\to l^{+}l^{-}$: An Update,” Nucl. Phys. B 548 (1999) 309–327, arXiv:hep-ph/9901288.
  * [62] P. Ball and R. Zwicky, “New results on $B\to\pi,K,\eta$ decay formfactors from light-cone sum rules,” Phys. Rev. D 71 (2005) 014015, arXiv:hep-ph/0406232.
  * [63] P. Ball and R. Zwicky, “$B_{d,s}\to\rho,\omega,K^{*},\phi$ decay form-factors from light-cone sum rules revisited,” Phys. Rev. D 71 (2005) 014029, arXiv:hep-ph/0412079.
  * [64] A. Khodjamirian, T. Mannel, A. A. Pivovarov, and Y. M. Wang, “Charm-loop effect in $B\to K^{(*)}\ell^{+}\ell^{-}$ and $B\to K^{*}\gamma$,” JHEP 09 (2010) 089, arXiv:1006.4945 [hep-ph].
  * [65] J. Brod, M. Gorbahn, and E. Stamou, “Two-Loop Electroweak Corrections for the $K\to\pi\nu\bar{\nu}$ Decays,” Phys. Rev. D 83 (2011) 034030, arXiv:1009.0947 [hep-ph].
  * [66] HPQCD Collaboration, C. Bouchard, G. P. Lepage, C. Monahan, H. Na, and J. Shigemitsu, “Rare decay $B\to K\ell^{+}\ell^{-}$ form factors from lattice QCD,” Phys. Rev. D 88 no. 5, (2013) 054509, arXiv:1306.2384 [hep-lat]. [Erratum: Phys.Rev.D 88, 079901 (2013)].
  * [67] R. R. Horgan, Z. Liu, S. Meinel, and M. Wingate, “Lattice QCD calculation of form factors describing the rare decays $B\to K^{*}\ell^{+}\ell^{-}$ and $B_{s}\to\phi\ell^{+}\ell^{-}$,” Phys. Rev. D 89 no. 9, (2014) 094501, arXiv:1310.3722 [hep-lat].
  * [68] W. Altmannshofer, A. J. Buras, D. M. Straub, and M. Wick, “New strategies for New Physics search in $B\to K^{*}\nu\bar{\nu}$, $B\to K\nu\bar{\nu}$ and $B\to X_{s}\nu\bar{\nu}$ decays,” JHEP 04 (2009) 022, arXiv:0902.0160 [hep-ph].
  * [69] A. J. Buras, J. Girrbach-Noe, C. Niehoff, and D. M. Straub, “$B\to{K}^{\left(\ast\right)}\nu\overline{\nu}$ decays in the Standard Model and beyond,” JHEP 02 (2015) 184, arXiv:1409.4557 [hep-ph].
  * [70] T. Blake, G. Lanfranchi, and D. M. Straub, “Rare $B$ Decays as Tests of the Standard Model,” Prog. Part. Nucl. Phys. 92 (2017) 50–91, arXiv:1606.00916 [hep-ph].
  * [71] Belle Collaboration, O. Lutz et al., “Search for $B\to h^{(*)}\nu\bar{\nu}$ with the full Belle $\Upsilon(4S)$ data sample,” Phys. Rev. D 87 no. 11, (2013) 111103, arXiv:1303.3719 [hep-ex].
  * [72] BaBar Collaboration, J. P. Lees et al., “Search for $B\to K^{(*)}\nu\overline{\nu}$ and invisible quarkonium decays,” Phys. Rev. D 87 no. 11, (2013) 112005, arXiv:1303.7465 [hep-ex].
  * [73] Belle Collaboration, J. Grygier et al., “Search for $\bm{B\to h\nu\bar{\nu}}$ decays with semileptonic tagging at Belle,” Phys. Rev. D 96 no. 9, (2017) 091101, arXiv:1702.03224 [hep-ex]. [Addendum: Phys.Rev.D 97, 099902 (2018)].
  * [74] Belle-II Collaboration, W. Altmannshofer et al., “The Belle II Physics Book,” PTEP 2019 no. 12, (2019) 123C01, arXiv:1808.10567 [hep-ex]. [Erratum: PTEP 2020, 029201 (2020)].
  * [75] M. Bauer and M. Neubert, “Minimal Leptoquark Explanation for the $R_{D^{(*)}}$ , $R_{K}$ , and $(g-2)_{\mu}$ Anomalies,” Phys. Rev. Lett. 116 no. 14, (2016) 141802, arXiv:1511.01900 [hep-ph].
  * [76] D. Bečirević, N. Košnik, O. Sumensari, and R. Zukanovich Funchal, “Palatable Leptoquark Scenarios for Lepton Flavor Violation in Exclusive $b\to s\ell_{1}\ell_{2}$ modes,” JHEP 11 (2016) 035, arXiv:1608.07583 [hep-ph].
  * [77] T. S. Roussy et al., “A new bound on the electron’s electric dipole moment,” Science 381 (2023) 46, arXiv:2212.11841 [physics.atom-ph].
  * [78] C. J. Ho, J. A. Devlin, I. M. Rabey, P. Yzombard, J. Lim, S. C. Wright, N. J. Fitch, E. A. Hinds, M. R. Tarbutt, and B. E. Sauer, “New techniques for a measurement of the electron’s electric dipole moment,” New J. Phys. 22 no. 5, (2020) 053031, arXiv:2002.02332 [physics.atom-ph].
  * [79] N. J. Fitch, J. Lim, E. A. Hinds, B. E. Sauer, and M. R. Tarbutt, “Methods for measuring the electron’s electric dipole moment using ultracold YbF molecules,” Quantum Sci. Technol. 6 no. 1, (2021) 014006, arXiv:2009.00346 [physics.atom-ph].
  * [80] MEG Collaboration, A. M. Baldini et al., “Search for the lepton flavour violating decay $\mu^{+}\rightarrow\mathrm{e}^{+}\gamma$ with the full dataset of the MEG experiment,” Eur. Phys. J. C 76 no. 8, (2016) 434, arXiv:1605.05081 [hep-ex].
  * [81] MEG II Collaboration, A. Baldini et al., “The design of the MEG II experiment,” Eur. Phys. J. C 78 no. 5, (2018) 380, arXiv:1801.04688 [physics.ins-det].
  * [82] SINDRUM II Collaboration, W. H. Bertl et al., “A Search for muon to electron conversion in muonic gold,” Eur. Phys. J. C 47 (2006) 337–346.
  * [83] Mu2e Collaboration, L. Bartoszek et al., “Mu2e Technical Design Report,” arXiv:1501.05241 [physics.ins-det].
  * [84] Mu2e Collaboration, F. Abusalma et al., “Expression of Interest for Evolution of the Mu2e Experiment,” arXiv:1802.02599 [physics.ins-det].
  * [85] Belle Collaboration, A. Abdesselam et al., “Search for lepton-flavor-violating tau-lepton decays to $\ell\gamma$ at Belle,” JHEP 10 (2021) 19, arXiv:2103.12994 [hep-ex].
  * [86] Belle-II Collaboration, L. Aggarwal et al., “Snowmass White Paper: Belle II physics reach and plans for the next decade and beyond,” arXiv:2207.06307 [hep-ex].
  * [87] S. Banerjee, “Searches for Lepton Flavor Violation in Tau Decays at Belle II,” Universe 8 no. 9, (2022) 480, arXiv:2209.11639 [hep-ex].
  * [88] NA62 Collaboration, E. Cortina Gil et al., “Measurement of the very rare K+→${\pi}^{+}\nu\overline{\nu}$ decay,” JHEP 06 (2021) 093, arXiv:2103.15389 [hep-ex].
  * [89] NA62, KLEVER Collaboration, “Rare decays at the CERN high-intensity kaon beam facility,” arXiv:2009.10941 [hep-ex].
  * [90] A. Cerri et al., “Report from Working Group 4: Opportunities in Flavour Physics at the HL-LHC and HE-LHC,” CERN Yellow Rep. Monogr. 7 (2019) 867–1158, arXiv:1812.07638 [hep-ph].
  * [91] A. J. Buras, D. Buttazzo, J. Girrbach-Noe, and R. Knegjens, “${K}^{+}\to{\pi}^{+}\nu\overline{\nu}$ and ${K}_{L}\to{\pi}^{0}\nu\overline{\nu}$ in the Standard Model: status and perspectives,” JHEP 11 (2015) 033, arXiv:1503.02693 [hep-ph].
  * [92] Particle Data Group Collaboration, R. L. Workman et al., “Review of Particle Physics,” PTEP 2022 (2022) 083C01.
  * [93] Muon g-2 Collaboration, G. W. Bennett et al., “Final Report of the Muon E821 Anomalous Magnetic Moment Measurement at BNL,” Phys. Rev. D 73 (2006) 072003, arXiv:hep-ex/0602035.
  * [94] Muon g-2 Collaboration, B. Abi et al., “Measurement of the Positive Muon Anomalous Magnetic Moment to 0.46 ppm,” Phys. Rev. Lett. 126 no. 14, (2021) 141801, arXiv:2104.03281 [hep-ex].
  * [95] S. Borsanyi et al., “Leading hadronic contribution to the muon magnetic moment from lattice QCD,” Nature 593 no. 7857, (2021) 51–55, arXiv:2002.12347 [hep-lat].
  * [96] chiQCD Collaboration, G. Wang, T. Draper, K.-F. Liu, and Y.-B. Yang, “Muon g-2 with overlap valence fermions,” arXiv:2204.01280 [hep-lat].
  * [97] M. Cè et al., “Window observable for the hadronic vacuum polarization contribution to the muon g-2 from lattice QCD,” Phys. Rev. D 106 no. 11, (2022) 114502, arXiv:2206.06582 [hep-lat].
  * [98] Extended Twisted Mass Collaboration, C. Alexandrou et al., “Lattice calculation of the short and intermediate time-distance hadronic vacuum polarization contributions to the muon magnetic moment using twisted-mass fermions,” Phys. Rev. D 107 no. 7, (2023) 074506, arXiv:2206.15084 [hep-lat].
  * [99] Fermilab Lattice, MILC, HPQCD Collaboration, C. T. H. Davies et al., “Windows on the hadronic vacuum polarization contribution to the muon anomalous magnetic moment,” Phys. Rev. D 106 no. 7, (2022) 074509, arXiv:2207.04765 [hep-lat].
  * [100] A. Bazavov et al., “Light-quark connected intermediate-window contributions to the muon $g-2$ hadronic vacuum polarization from lattice QCD,” arXiv:2301.08274 [hep-lat].
  * [101] T. Blum et al., “An update of Euclidean windows of the hadronic vacuum polarization,” arXiv:2301.08696 [hep-lat].
  * [102] CMD-3 Collaboration, F. V. Ignatov et al., “Measurement of the $e^{+}e^{-}\to\pi^{+}\pi^{-}$ cross section from threshold to 1.2 GeV with the CMD-3 detector,” arXiv:2302.08834 [hep-ex].
  * [103] D. Stockinger, “The Muon Magnetic Moment and Supersymmetry,” J. Phys. G 34 (2007) R45–R92, arXiv:hep-ph/0609168.
  * [104] M. Blanke, A. J. Buras, B. Duling, A. Poschenrieder, and C. Tarantino, “Charged Lepton Flavour Violation and (g-2)(mu) in the Littlest Higgs Model with T-Parity: A Clear Distinction from Supersymmetry,” JHEP 05 (2007) 013, arXiv:hep-ph/0702136.
  * [105] M. Pospelov, “Secluded U(1) below the weak scale,” Phys. Rev. D 80 (2009) 095002, arXiv:0811.1030 [hep-ph].
  * [106] F. Feruglio, C. Hagedorn, Y. Lin, and L. Merlo, “Lepton Flavour Violation in Models with A(4) Flavour Symmetry,” Nucl. Phys. B 809 (2009) 218–243, arXiv:0807.3160 [hep-ph].
  * [107] R. Dermisek and A. Raval, “Explanation of the Muon g-2 Anomaly with Vectorlike Leptons and its Implications for Higgs Decays,” Phys. Rev. D 88 (2013) 013017, arXiv:1305.3522 [hep-ph].
  * [108] P. Agrawal, Z. Chacko, and C. B. Verhaaren, “Leptophilic Dark Matter and the Anomalous Magnetic Moment of the Muon,” JHEP 08 (2014) 147, arXiv:1402.7369 [hep-ph].
  * [109] L. Calibbi, P. Paradisi, and R. Ziegler, “Lepton Flavor Violation in Flavored Gauge Mediation,” Eur. Phys. J. C 74 no. 12, (2014) 3211, arXiv:1408.0754 [hep-ph].
  * [110] L. Calibbi, R. Ziegler, and J. Zupan, “Minimal models for dark matter and the muon g-2 anomaly,” JHEP 07 (2018) 046, arXiv:1804.00009 [hep-ph].
  * [111] S. Saad, “Combined explanations of $(g-2)_{\mu}$, $R_{D^{(*)}}$, $R_{K^{(*)}}$ anomalies in a two-loop radiative neutrino mass model,” Phys. Rev. D 102 no. 1, (2020) 015019, arXiv:2005.04352 [hep-ph].
  * [112] L. Calibbi, M. L. López-Ibáñez, A. Melis, and O. Vives, “Muon and electron $g-2$ and lepton masses in flavor models,” JHEP 06 (2020) 087, arXiv:2003.06633 [hep-ph].
  * [113] L. Calibbi, M. L. López-Ibáñez, A. Melis, and O. Vives, “Implications of the Muon g-2 result on the flavour structure of the lepton mass matrix,” Eur. Phys. J. C 81 no. 10, (2021) 929, arXiv:2104.03296 [hep-ph].
  * [114] P. Fileviez Perez, C. Murgui, and A. D. Plascencia, “Leptoquarks and matter unification: Flavor anomalies and the muon g-2,” Phys. Rev. D 104 no. 3, (2021) 035041, arXiv:2104.11229 [hep-ph].
  * [115] M. L. López-Ibáñez, A. Melis, M. J. Pérez, M. H. Rahat, and O. Vives, “Constraining low-scale flavor models with (g-2)μ and lepton flavor violation,” Phys. Rev. D 105 no. 3, (2022) 035021, arXiv:2112.11455 [hep-ph].
  * [116] B. Diaz, M. Schmaltz, and Y.-M. Zhong, “The leptoquark Hunter’s guide: Pair production,” JHEP 10 (2017) 097, arXiv:1706.05033 [hep-ph].
  * [117] M. Schmaltz and Y.-M. Zhong, “The leptoquark Hunter’s guide: large coupling,” JHEP 01 (2019) 132, arXiv:1810.10017 [hep-ph].
  * [118] B. C. Allanach, B. Gripaios, and T. You, “The case for future hadron colliders from $B\to K^{(*)}\mu^{+}\mu^{-}$ decays,” JHEP 03 (2018) 021, arXiv:1710.06363 [hep-ph].
  * [119] B. C. Allanach, T. Corbett, and M. Madigan, “Sensitivity of Future Hadron Colliders to Leptoquark Pair Production in the Di-Muon Di-Jets Channel,” Eur. Phys. J. C 80 no. 2, (2020) 170, arXiv:1911.04455 [hep-ph].
  * [120] P. Bandyopadhyay, S. Dutta, M. Jakkapu, and A. Karan, “Distinguishing Leptoquarks at the LHC/FCC,” Nucl. Phys. B 971 (2021) 115524, arXiv:2007.12997 [hep-ph].
  * [121] G. Hiller, D. Loose, and I. Nišandžić, “Flavorful leptoquarks at the LHC and beyond: spin 1,” JHEP 06 (2021) 080, arXiv:2103.12724 [hep-ph].
  * [122] G.-y. Huang, S. Jana, F. S. Queiroz, and W. Rodejohann, “Probing the RK(*) anomaly at a muon collider,” Phys. Rev. D 105 no. 1, (2022) 015013, arXiv:2103.01617 [hep-ph].
  * [123] P. Asadi, R. Capdevilla, C. Cesarotti, and S. Homiller, “Searching for leptoquarks at future muon colliders,” JHEP 10 (2021) 182, arXiv:2104.05720 [hep-ph].
  * [124] P. Bandyopadhyay, A. Karan, R. Mandal, and S. Parashar, “Distinguishing signatures of scalar leptoquarks at hadron and muon colliders,” Eur. Phys. J. C 82 no. 10, (2022) 916, arXiv:2108.06506 [hep-ph].
  * [125] S. Qian, C. Li, Q. Li, F. Meng, J. Xiao, T. Yang, M. Lu, and Z. You, “Searching for heavy leptoquarks at a muon collider,” JHEP 12 (2021) 047, arXiv:2109.01265 [hep-ph].
  * [126] S. Parashar, A. Karan, Avnish, P. Bandyopadhyay, and K. Ghosh, “Phenomenology of scalar leptoquarks at the LHC in explaining the radiative neutrino masses, muon g-2, and lepton flavor violating observables,” Phys. Rev. D 106 no. 9, (2022) 095040, arXiv:2209.05890 [hep-ph].
  * [127] Muon Collider Collaboration, J. de Blas et al., “The physics case of a 3 TeV muon collider stage,” arXiv:2203.07261 [hep-ph].
  * [128] COMET Collaboration, R. Abramishvili et al., “COMET Phase-I Technical Design Report,” PTEP 2020 no. 3, (2020) 033C01, arXiv:1812.09018 [physics.ins-det].
  * [129] COMET Collaboration, J. Angélique et al., “COMET - A submission to the 2020 update of the European Strategy for Particle Physics on behalf of the COMET collaboration,” arXiv:1812.07824 [hep-ex].
  * [130] Mu2e-II Collaboration, K. Byrum et al., “Mu2e-II: Muon to electron conversion with PIP-II,” in Snowmass 2021.  3, 2022.  arXiv:2203.07569 [hep-ex].
  * [131] C. Group Collaboration, M. Aoki et al., “A New Charged Lepton Flavor Violation Program at Fermilab,” in Snowmass 2021.  3, 2022.  arXiv:2203.08278 [hep-ex].
  * [132] S. A. R. Ellis and A. Pierce, “Impact of Future Lepton Flavor Violation Measurements in the Minimal Supersymmetric Standard Model,” Phys. Rev. D 94 no. 1, (2016) 015014, arXiv:1604.01419 [hep-ph].
  * [133] S. Homiller, Q. Lu, and M. Reece, “Complementary signals of lepton flavor violation at a high-energy muon collider,” JHEP 07 (2022) 036, arXiv:2203.08825 [hep-ph].
  * [134] A. Baldini et al., “A submission to the 2020 update of the European Strategy for Particle Physics on behalf of the COMET, MEG, Mu2e and Mu3e collaborations,” arXiv:1812.06540 [hep-ex].
  * [135] ACME Collaboration, V. Andreev et al., “Improved limit on the electric dipole moment of the electron,” Nature 562 no. 7727, (2018) 355–360.
  * [136] R. Alarcon et al., “Electric dipole moments and the search for new physics,” in Snowmass 2021.  3, 2022.  arXiv:2203.08103 [hep-ph].
  * [137] UTfit Collaboration, M. Bona et al., “Model-independent constraints on $\Delta F=2$ operators and the scale of new physics,” JHEP 03 (2008) 049, arXiv:0707.0636 [hep-ph].
  * [138] UTfit Collaboration, F. Ferrari, “Updates in the Unitarity Triangle fits with UTfit,” PoS CKM2021 (2023) 078.
  * [139] E. Goudzovski et al., “New physics searches at kaon and hyperon factories,” Rept. Prog. Phys. 86 no. 1, (2023) 016201, arXiv:2201.07805 [hep-ph].
  * [140] K. Aoki et al., “Extension of the J-PARC Hadron Experimental Facility: Third White Paper,” arXiv:2110.04462 [nucl-ex].
  * [141] J. Hisano, T. Moroi, K. Tobe, and M. Yamaguchi, “Lepton flavor violation via right-handed neutrino Yukawa couplings in supersymmetric standard model,” Phys. Rev. D 53 (1996) 2442–2459, arXiv:hep-ph/9510309.
  * [142] J. R. Ellis, J. S. Lee, and A. Pilaftsis, “Electric Dipole Moments in the MSSM Reloaded,” JHEP 10 (2008) 049, arXiv:0808.1819 [hep-ph].
  * [143] A. Crivellin, M. Hoferichter, and P. Schmidt-Wellenburg, “Combined explanations of $(g-2)_{\mu,e}$ and implications for a large muon EDM,” Phys. Rev. D 98 no. 11, (2018) 113002, arXiv:1807.11484 [hep-ph].
  * [144] C. Cesarotti, Q. Lu, Y. Nakai, A. Parikh, and M. Reece, “Interpreting the Electron EDM Constraint,” JHEP 05 (2019) 059, arXiv:1810.07736 [hep-ph].
  * [145] Y. Nakai and M. Reece, “Electric Dipole Moments in Natural Supersymmetry,” JHEP 08 (2017) 031, arXiv:1612.08090 [hep-ph].
  * [146] Y. Okada, K.-i. Okumura, and Y. Shimizu, “Mu –$>$ e gamma and mu –$>$ 3 e processes with polarized muons and supersymmetric grand unified theories,” Phys. Rev. D 61 (2000) 094001, arXiv:hep-ph/9906446.
  * [147] Y. Kuno and Y. Okada, “Muon decay and physics beyond the standard model,” Rev. Mod. Phys. 73 (2001) 151–202, arXiv:hep-ph/9909265.
  * [148] R. Kitano, M. Koike, and Y. Okada, “Detailed calculation of lepton flavor violating muon electron conversion rate for various nuclei,” Phys. Rev. D 66 (2002) 096002, arXiv:hep-ph/0203110. [Erratum: Phys.Rev.D 76, 059902 (2007)].
  * [149] S. Fajfer, J. F. Kamenik, I. Nisandzic, and J. Zupan, “Implications of Lepton Flavor Universality Violations in B Decays,” Phys. Rev. Lett. 109 (2012) 161801, arXiv:1206.1872 [hep-ph].
  * [150] D. Bečirević, O. Sumensari, and R. Zukanovich Funchal, “Lepton flavor violation in exclusive $b\rightarrow s$ decays,” Eur. Phys. J. C 76 no. 3, (2016) 134, arXiv:1602.00881 [hep-ph].
  * [151] Y. Sakaki, M. Tanaka, A. Tayduganov, and R. Watanabe, “Testing leptoquark models in $\bar{B}\to D^{(*)}\tau\bar{\nu}$,” Phys. Rev. D 88 no. 9, (2013) 094012, arXiv:1309.0301 [hep-ph].
  * [152] M. Freytsis, Z. Ligeti, and J. T. Ruderman, “Flavor models for $\bar{B}\to D^{(*)}\tau\bar{\nu}$,” Phys. Rev. D 92 no. 5, (2015) 054018, arXiv:1506.08896 [hep-ph].
  * [153] Y. Cai, J. Gargalionis, M. A. Schmidt, and R. R. Volkas, “Reconsidering the One Leptoquark solution: flavor anomalies and neutrino mass,” JHEP 10 (2017) 047, arXiv:1704.05849 [hep-ph].
  * [154] BaBar Collaboration, B. Aubert et al., “Observation of the semileptonic decays $B\to D^{*}\tau^{-}\bar{\nu}$( $\tau^{)}$ and evidence for $B\to D\tau^{-}\bar{\nu}$( $\tau^{)}$,” Phys. Rev. Lett. 100 (2008) 021801, arXiv:0709.1698 [hep-ex].
  * [155] Belle Collaboration, A. Bozek et al., “Observation of $B^{+}\to\bar{D}^{*}0\tau^{+}\nu_{\tau}$ and Evidence for $B^{+}\to\bar{D}^{0}\tau^{+}\nu_{\tau}$ at Belle,” Phys. Rev. D 82 (2010) 072005, arXiv:1005.2302 [hep-ex].
  * [156] BaBar Collaboration, J. P. Lees et al., “Evidence for an excess of $\bar{B}\to D^{(*)}\tau^{-}\bar{\nu}_{\tau}$ decays,” Phys. Rev. Lett. 109 (2012) 101802, arXiv:1205.5442 [hep-ex].
  * [157] BaBar Collaboration, J. P. Lees et al., “Measurement of an Excess of $\bar{B}\to D^{(*)}\tau^{-}\bar{\nu}_{\tau}$ Decays and Implications for Charged Higgs Bosons,” Phys. Rev. D 88 no. 7, (2013) 072012, arXiv:1303.0571 [hep-ex].
  * [158] LHCb Collaboration, R. Aaij et al., “Measurement of the ratio of branching fractions $\mathcal{B}(\bar{B}^{0}\to D^{*+}\tau^{-}\bar{\nu}_{\tau})/\mathcal{B}(\bar{B}^{0}\to D^{*+}\mu^{-}\bar{\nu}_{\mu})$,” Phys. Rev. Lett. 115 no. 11, (2015) 111803, arXiv:1506.08614 [hep-ex]. [Erratum: Phys.Rev.Lett. 115, 159901 (2015)].
  * [159] Belle Collaboration, M. Huschle et al., “Measurement of the branching ratio of $\bar{B}\to D^{(\ast)}\tau^{-}\bar{\nu}_{\tau}$ relative to $\bar{B}\to D^{(\ast)}\ell^{-}\bar{\nu}_{\ell}$ decays with hadronic tagging at Belle,” Phys. Rev. D 92 no. 7, (2015) 072014, arXiv:1507.03233 [hep-ex].
  * [160] A. Abdesselam et al., “Measurement of the $\tau$ lepton polarization in the decay ${\bar{B}}\rightarrow D^{*}\tau^{-}{\bar{\nu}_{\tau}}$,” arXiv:1608.06391 [hep-ex].
  * [161] M. Tanaka and R. Watanabe, “New physics in the weak interaction of $\bar{B}\to D^{(*)}\tau\bar{\nu}$,” Phys. Rev. D 87 no. 3, (2013) 034028, arXiv:1212.1878 [hep-ph].
  * [162] P. Asadi, M. R. Buckley, and D. Shih, “Asymmetry Observables and the Origin of $R_{D^{(*)}}$ Anomalies,” Phys. Rev. D 99 no. 3, (2019) 035015, arXiv:1810.06597 [hep-ph].
  * [163] D. Bardhan, P. Byakti, and D. Ghosh, “A closer look at the RD and R${}_{D^{*}}$ anomalies,” JHEP 01 (2017) 125, arXiv:1610.03038 [hep-ph].
  * [164] A. J. Buras, F. Schwab, and S. Uhlig, “Waiting for precise measurements of $K^{+}\to\pi^{+}\nu\bar{\nu}$ and $K_{L}\to\pi^{0}\nu\bar{\nu}$,” Rev. Mod. Phys. 80 (2008) 965–1007, arXiv:hep-ph/0405132.
  * [165] Y. Grossman and Y. Nir, “$K_{L}\to\pi^{0}\nu\bar{\nu}$ beyond the standard model,” Phys. Lett. B 398 (1997) 163–168, arXiv:hep-ph/9701313.
  * [166] KOTO Collaboration, J. K. Ahn et al., “Study of the $K_{L}\to\pi^{0}\nu\bar{\nu}$ Decay at the J-PARC KOTO Experiment,” Phys. Rev. Lett. 126 no. 12, (2021) 121801, arXiv:2012.07571 [hep-ex].
  * [167] ATLAS Collaboration, G. Aad et al., “Search for the lepton flavor violating decay Z→e$\mu$ in pp collisions at $\sqrt{s}$ TeV with the ATLAS detector,” Phys. Rev. D 90 no. 7, (2014) 072010, arXiv:1408.5774 [hep-ex].
  * [168] D. Bečirević and O. Sumensari, “A leptoquark model to accommodate $R_{K}^{\mathrm{exp}}<R_{K}^{\mathrm{SM}}$ and $R_{K^{\ast}}^{\mathrm{exp}}<R_{K^{\ast}}^{\mathrm{SM}}$,” JHEP 08 (2017) 104, arXiv:1704.05835 [hep-ph].
  * [169] P. Arnan, D. Becirevic, F. Mescia, and O. Sumensari, “Probing low energy scalar leptoquarks by the leptonic $W$ and $Z$ couplings,” JHEP 02 (2019) 109, arXiv:1901.06315 [hep-ph].
  * [170] A. Efrati, A. Falkowski, and Y. Soreq, “Electroweak constraints on flavorful effective theories,” JHEP 07 (2015) 018, arXiv:1503.07872 [hep-ph].
  * [171] ALEPH, DELPHI, L3, OPAL, SLD, LEP Electroweak Working Group, SLD Electroweak Group, SLD Heavy Flavour Group Collaboration, S. Schael et al., “Precision electroweak measurements on the $Z$ resonance,” Phys. Rept. 427 (2006) 257–454, arXiv:hep-ex/0509008.
  * [172] A. Juttner, “Progress in kaon physics on the lattice,” PoS LATTICE2007 (2007) 014, arXiv:0711.1239 [hep-lat].
  * [173] R. J. Dowdall, C. T. H. Davies, R. R. Horgan, G. P. Lepage, C. J. Monahan, J. Shigemitsu, and M. Wingate, “Neutral B-meson mixing from full lattice QCD at the physical point,” Phys. Rev. D 100 no. 9, (2019) 094508, arXiv:1907.01025 [hep-lat].
  * [174] B. Grinstein, “TASI-2013 Lectures on Flavor Physics,” in Theoretical Advanced Study Institute in Elementary Particle Physics: Particle Physics: The Higgs Boson and Beyond.  1, 2015.  arXiv:1501.05283 [hep-ph].
  * [175] A. Lenz, U. Nierste, J. Charles, S. Descotes-Genon, A. Jantsch, C. Kaufhold, H. Lacker, S. Monteil, V. Niess, and S. T’Jampens, “Anatomy of New Physics in $B-\bar{B}$ mixing,” Phys. Rev. D 83 (2011) 036004, arXiv:1008.1593 [hep-ph].
  * [176] G. Buchalla, A. J. Buras, and M. E. Lautenbacher, “Weak decays beyond leading logarithms,” Rev. Mod. Phys. 68 (1996) 1125–1144, arXiv:hep-ph/9512380.
  * [177] A. J. Buras, “Flavor physics and CP violation,” in 2004 European School of High-Energy Physics, pp. 95–168.  5, 2005.  arXiv:hep-ph/0505175.
  * [178] E. Golowich, J. Hewett, S. Pakvasa, and A. A. Petrov, “Implications of $D^{0}$ \- $\bar{D}^{0}$ Mixing for New Physics,” Phys. Rev. D 76 (2007) 095009, arXiv:0705.3650 [hep-ph].
  * [179] A. Bazavov et al., “Short-distance matrix elements for $D^{0}$-meson mixing for $N_{f}=2+1$ lattice QCD,” Phys. Rev. D 97 no. 3, (2018) 034513, arXiv:1706.04622 [hep-lat].