close

Monthly Archive

You are currently browsing the monthly archive for August 2024.

Erdos problem #385, the parity problem, and Siegel zeroes

19 August, 2024 in expository, math.NT | Tags: , , | by | 24 comments

The Erdös problem site was created last year, and announced earlier this year on this blog. Every so often, I have taken a look at a random problem from the site for fun. A few times, I was able to make progress on one of the problems, leading to a couple papers; but the more common outcome is that I play around with the problem for a while, see why the problem is difficult, and then eventually give up and do something else. But, as is common in this field, I don’t make public the observations that I made, and the next person who looks at the same problem would likely have to go through the same process of trial and error to work out what the main obstructions that are present are.

So, as an experiment, I thought I would record here my preliminary observations on one such problem – Erdös problem #385 – to discuss why it looks difficult to solve with our current understanding of the primes. Here is the problem:

Problem 1 (Erdös Problem #385) Let

\displaystyle F(n) =\max_{\stackrel{m<n}{m\hbox{\ composite}}} m+p(m),

where {p(m)} is the least prime divisor of {m} . Is it true that {F(n)>n} for all sufficiently large {n}? Does {F(n)-n \rightarrow \infty} as {n \rightarrow \infty}?

This problem is mentioned on page 73 of this 1979 paper of Erdös (where he attributes the problem to an unpublished work of Eggelton, Erdös, and Selfridge that, to my knowledge, has never actually appeared), as well as briefly in page 92 of this 1980 paper of Erdös and Graham.

At first glance, this looks like a somewhat arbitrary problem (as many of Erdös’s problems initially do), as the function {F} is not obviously related to any other well-known function or problem. However, it turns out that this problem is closely related to the parity barrier in sieve theory (as discussed in this previous post), with the possibility of Siegel zeroes presenting a particular obstruction. I suspect that Erdös was well aware of this connection; certainly he mentions the relation with questions on gaps between primes (or almost primes), which is in turn connected to the parity problem and Siegel zeroes (as is discussed recently in my paper with Banks and Ford, and in more depth in these papers of Ford and of Granville).

Let us now explore the problem further. Let us call a natural number {n} bad if {F(n) \leq n}, so the first part of the problem is asking whether there exist bad numbers that are sufficiently large. We unpack the definitions: {n} is bad if and only if {m+p(m) \leq n} for any composite {m}, so placing {m} in intervals of the form {[n-h,n]} we are asking to show that

\displaystyle p(m) \leq h \hbox{ for all composite } m \in [n-h, n]

for each {1 \leq h \leq n}. To put it another way, the badness of {n} asserts that for each {1 \leq h \leq n} that the residue classes {0 \hbox{ mod } p} for {p \leq h} cover all the natural numbers in the interval {[n-h,n]} except for the primes.

It is now natural to try to understand this problem for a specific choice of interval {h} as a function of {n}. If {h} is large in the sense that {h > \sqrt{n}}, then the claimed covering property is automatic, since every composite number less than or equal to {n} has a prime factor less than or equal to {\sqrt{n}}. On the other hand, for {h} very small, in particular {h = o(\log n)}, it is also possible to find {n} with this property. Indeed, if one takes {n} to lie in the residue class {0 \hbox{ mod } \prod_{p \leq h}}, then we see that the residue classes cover all of {[n-h,n]} except for {n-1}, and from Linnik’s theorem we can ensure that {n-1} is prime. Thus, to rule out bad numbers, we need to understand the covering problem at intermediate scales {\log n \ll h \ll \sqrt{n}}.

A key case is when {h = n^{1/u}} for some {2 < u < 3}. Here, the residue classes {0 \hbox{ mod } p} for {p \leq h} sieve out everything in {[n-h,n]} except for primes and semiprimes, and specifically the semiprimes that are product of two primes between {n^{1/u}} and {n^{1-1/u}}. If one can show for some {2 < u < 3} that the largest gap between semiprimes in say {[x,2x]} with prime factors in {[x^{1/u}, x^{1-1/u}]} is {o( x^{1/u} )}, then this would affirmatively answer the first part of this problem (and also the second). This is certainly very plausible – it would follow from a semiprime version of the Cramér conjecture (and this would also make the more precise prediction {F(n) = n + n^{1/2-o(1)}}) – but remains well out of reach for now. Even assuming the Riemann hypothesis, the best upper bound on prime gaps in {[x,2x]} is {O( \sqrt{x} \log x )}, and the best upper bound on semiprime gaps is not significantly better than this – in particular, one cannot reach {x^{1/u}} for any {2 < u < 3}. (There is a remote possibility that an extremely delicate analysis near {u=2}, together with additional strong conjectures on the zeta function, such as a sufficiently quantitative version of the GUE hypothesis, may barely be able to resolve this problem, but I am skeptical of this, absent some further major breakthrough in analytic number theory.)

Given that multiplicative number theory does not seem powerful enough (even on RH) to resolve these problems, the other main approach would be to use sieve theory. In this theory, we do not really know how to exploit the specific location of the interval {[n-h,n]} or the specific congruence classes used, so one can study the more general problem of trying to cover an interval {I} of length {h} by one residue class mod {p} for each {p \leq h}, and only leaving a small number of survivors which could potentially be classified as “primes”. The discussion of the small {h} case already reveals a problem with this level of generality: one can sieve out the interval {[-h, 1]} by the residue classes {0 \hbox{ mod } p} for {p \leq h}, and leave only one survivor, {-1}. Indeed, thanks to known bounds on Jacobsthal’s function, one can be more efficient than this; for instance, using equation (1.2) from this paper of Ford, Green, Konyagin, Maynard, and myself, it is possible to completely sieve out any interval of sufficiently large length {h} using only those primes {p} up to {O(\frac{h \log\log h}{\log h \log\log\log h})}. On the other hand, from the work of Iwaniec, we know that sieving up to {o(h^{1/2})} is insufficient to completely sieve out such an interval; related to this, if one only sieves up to {h^{1/u}} for some {2 < u < 3}, the linear sieve (see e.g., Theorem 2 of this previous blog post) shows that one must have at least {(f(u)+o(1)) \frac{h}{\log h}} survivors, where {f(u)} can be given explicitly in the regime {2 < u < 3} by the formula

\displaystyle f(u) := \frac{2e^\gamma}{u} \log(u-1).

These lower bounds are not believed to be best possible. For instance, the Maier–Pomerance conjecture on Jacobsthal’s function would indicate that one needs to sieve out primes up to {\gg h/\log^2 h} in order to completely sieve out an interval of length {h}, and it is also believed that sieving up to {h^{1-\varepsilon}} should leave {\gg_\varepsilon h/\log h} survivors, although even these strong conjectures are not enough to positively resolve this problem, since we are permitted to sieve all the way up to {h} (and we are allowed to leave every prime number as a survivor, which in view of the Brun–Titchmarsh theorem could permit as many as {O(h/\log n)} survivors).

Unfortunately, as discussed in this previous blog post, the parity problem blocks such improvements from taking place from most standard analytic number theory methods, in particular sieve theory. A particularly dangerous enemy arises from Siegel zeroes. This is discussed in detail in the papers of of Ford and of Granville mentioned previously, but an informal discussion is as follows. If there is a Siegel zero associated to the quadratic character of some conductor {q}, this roughly speaking means that almost all primes {p} (in certain ranges) will be quadratic non-residues mod {q}. In particular, if one restricts attention to numbers {n} in a residue class {a \hbox{ mod } q} that is a quadratic residue, we then expect most numbers in this class to have an even number of prime factors, rather than an odd number.

This alters the effect of sieving in such residue classes. Consider for instance the classical sieve of Eratosthenes. If one sieves out {0 \hbox{ mod } p} for each prime {p \leq \sqrt{h}}, the sieve of Eratosthenes tells us that the surviving elements of {[1,h]} are simply the primes between {\sqrt{h}} and {h}, of which there are about {h/\log h} many. However, if one restricts attention to {[1,h] \cap a \hbox{ mod } q} for a quadratic residue class {a \hbox{ mod } q} (and taking {h} to be somewhat large compared to {q}), then by the preceding discussion, this eliminates most primes, and so now sieving out {0 \hbox{ mod } p} should leave almost no survivors. Shifting this example by {a} and then dividing by {q}, one can end up with an example of an interval {I} of length {h} that can be sieved by residue classes {b_p \hbox{ mod } p} for each {p \leq \sqrt{h}} in such a manner as to leave almost no survivors (in particular, {o(h/\log h)} many). In the presence of a Siegel zero, it seems quite difficult to prevent this scenario from “infecting” the above problem, creating a bad scenario in which for all {\log n \ll h \ll \sqrt{n}}, the residue classes {0 \hbox{ mod } p} for {p \leq \sqrt{h}} already eliminate almost all elements of {[n-h,n]}, leaving it mathematically possible for the remaining survivors to either be prime, or eliminated by the remaining residue classes {0 \hbox{ mod } p} for {\sqrt{h} < p \leq h}.

Because of this, I suspect that it will not be possible to resolve this Erdös problem without a major breakthrough on the parity problem that (at a bare minimum) is enough to exclude the possibility of Siegel zeroes existing. (But it is not clear at all that Siegel zeroes are be the only “enemy” here, so absent a major advance in “inverse sieve theory”, one cannot simply assume GRH to run away from this problem).

— 0.1. Addendum: heuristics for Siegel zero scenarios —

This post also provides a good opportunity to refine some heuristics I had previously proposed regarding Siegel zeroes and their impact on various problems in analytic number theory. In this previous blog post, I wrote

“The parity problem can also be sometimes be overcome when there is an exceptional Siegel zero … [this] suggests that to break the parity barrier, we may assume without loss of generality that there are no Siegel zeroes.”

On the other hand, it was pointed out in a more recent article of Granville that (as with the current situation), Siegel zeroes can sometimes serve to enforce the parity barrier, rather than overcome it, and responds to my previous statement with the comment “this claim needs to be treated with caution, since its truth depends on the context”.

I actually agree with Granville here, and I propose here a synthesis of the two situations. In the absence of a Siegel zero, standard heuristic models in analytic number theory (such as the ones discussed in this post) typically suggest that a given quantity {X} of interest in number theory (e.g., the number of primes in a certain set) obey an asymptotic law of the form

\displaystyle X = \mathrm{Main\ term} + \mathrm{Error\ term}

where {\mathrm{Main\ term}} is generally fairly well understood, while {\mathrm{Error\ term}} is expected to fluctuate “randomly” (or more precisely, pseudorandomly) and thus be smaller than the main term. However, a major difficulty in analytic number theory is that we often cannot prevent a “conspiracy” from occurring in which the error term becomes as large as, or even larger than the main term: the fluctuations present in that term are often too poorly understood to be under good control. The parity barrier manifests by providing examples of analogous situations in which the error term is indeed as large as the main term (with an unfavorable sign).

However, the presence of a Siegel zero tends to “magnetize” the error term by pulling most of the fluctuations in a particular direction. In many situations, what this means is that one can obtain a refined asymptotic of the form

\displaystyle X = \mathrm{Main\ term} + \mathrm{Siegel\ correction} + \mathrm{Better\ error\ term}

where {\mathrm{Better\ error\ term}} now fluctuates less than the original {\mathrm{Error\ term}}, and in particular can (in some cases) be shown to be lower order than {\mathrm{Main\ term}}, while {\mathrm{Siegel\ correction}} is a new term that is often explicitly describable in terms of the exceptional character {\chi} associated to the Siegel zero, as well as the location {\beta} of the Siegel zero {L(\beta,\chi)=0}. A typical example is the problem of estimating the sum {\sum_{n \leq x: n = a\ (q)} \Lambda(n)} of primes in an arithmetic progression. The Siegel–Walfisz theorem gives a bound of the form

\displaystyle \sum_{n \leq x: n = a\ (q)} \Lambda(n) = \frac{x}{\varphi(q)} + O_A( x \log^{-A} x )

for any {A>0} (with an ineffective constant); in the regime {q = O(\log^{O(1)} x)} one can improve the error term to {O( x \exp(-c \log^{1/2} x) )}, but for large {q} one cannot do better than the Brun–Titchmarsh bound of {O(x / \varphi(q))}. However, when there is a Siegel zero {L(\beta,\chi)} in an appropriate range, we can obtain the refined bound

\displaystyle \sum_{n \leq x: n = a\ (q)} \Lambda(n) = \frac{x}{\varphi(q)} - \chi(a) 1_{q_0|q} 1_{(a,q)=1} \frac{x^{\beta-1}}{\beta} + O( x \exp(\log^{-c} x))

for some {c>0}, where {q_0} is the conductor of {\chi}; see e.g., Theorem 5.27 of Iwaniec–Kowalski. Thus we see the error term is much improved (and in fact can even be made effective), at the cost of introduicing a Siegel correction term which (for {\beta} close to {1} and {x} not too large) is of comparable size to the main term, and can either be aligned with or against the main term depending on the sign of {\chi(a)}.

The implications of this refined asymptotic then depend rather crucially on how the Siegel correction term is aligned with the main term, and also whether it is of comparable order or lower order. In many situations (particularly those concerning “average case” problems, in which one wants to understand the behavior for typical choices of parameters), the Siegel correction term ends up being lower order, and so one ends up with the situation described in my initial blog post, where we are able to get the predicted asymptotic {X \approx \mathrm{Main\ term}} in the Siegel zero case. However, as pointed out by Granville, there are other situations (particularly those involving “worst case” problems, in which some key parameter can be chosen adversarially) in which the Siegel correction term can align to completely cancel (or to highly reinforce) the main term. In such cases, the Siegel zero becomes a very concrete manifestation of the parity barrier, rather than a means to avoid it. (There is a tiny chance that there may be some sort of “repulsion” phenomenon in which having no semiprimes in {[n-h,n]} for one value of {h} somehow generates semiprimes in {[n-h',n]} for another value of {h'}, which would allow one to solve the problem without having to directly address the Siegel issue, but I don’t see how two such intervals could “communicate” in order to achieve such a repulsion effect.)

A result of Bui–Pratt–Zaharescu, and Erdös problem #437

9 August, 2024 in expository, math.NT | Tags: , , , | by | 14 comments

The following problem was posed by Erdös and Graham (and is listed as problem #437 on the Erdös problems website):

Problem 1 Let {1 \leq a_1 < \dots < a_k \leq x} be integers. How many of the partial products {a_1}, {a_1 a_2}, {\dots}, {a_1 \dots a_k} can be squares? Is it true that, for any {\varepsilon>0}, there can be more than {x^{1-\varepsilon}} squares?

If one lets {L(x)} denote the maximal number of squares amongst such partial products, it was observed in the paper of Erdös and Graham that the bound {L(x) = o(x)} is “trivial” (no proof was provided, but one can for instance argue using the fact that the number of integer solutions to hyperelliptic equations of the form {(n+h_1) \dots (n+h_d) = m^2} for fixed {h_1 < \dots < h_d} is quite sparse, and in fact finite for {d>2} thanks to Siegel’s theorem), and the problem then asks if {L(x) = x^{1-o(1)}}.

It turns out that this problem was essentially solved (though not explicitly) by a recently published paper of Bui, Pratt, and Zaharescu, who studied a closely related quantity {t_n} introduced by Erdös, Graham, and Selfridge (see also Problem B30 of Guy’s book), defined for any natural number {n} as the least natural number {t_n} such that some subset of {n+1,\dots,n+t_{n}}, when multiplied together with {n}, produced a square. Among the several results proven about {t_n} in that paper was the following:

Theorem 2 (Bui–Pratt–Zaharescu, Theorem 1.2) For {x} sufficiently large, there exist {\gg x \exp(-(3\sqrt{2}/2+o(1)) \sqrt{\log x} \sqrt{\log\log x})} integers {1 \leq n \leq x} such that {t_n \leq \exp((\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}.

The arguments were in fact quite elementary, with the main tool being the theory of smooth numbers (the theory of hyperelliptic equations is used elsewhere in the paper, but not for this particular result).

If one uses this result as a “black box”, then an easy greedy algorithm argument gives the lower bound

\displaystyle L(x) \geq x\exp(-(5\sqrt{2}/2+o(1)) \sqrt{\log x} \sqrt{\log\log x}),

but with a small amount of additional work, one can modify the proof of the theorem to give a slightly better bound:

Theorem 3 (Bounds for {L}) As {x \rightarrow \infty}, we have the lower bound

\displaystyle L(x) \geq x\exp(-(\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})

and the upper bound

\displaystyle L(x) \leq x\exp(-(1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x}).

In particular, for any {\varepsilon>0}, one has {L(x) \geq x^{1-\varepsilon}} for sufficiently large {x}.

The purpose of this blog post is to record this modification of the argument, which is short enough to present immediately. For a large {x}, let {u} denote the quantity

\displaystyle u := \sqrt{2} \sqrt{\log x} / \sqrt{\log\log x}.

We call a natural number {x^{1/u}}-smooth if all of its prime factors are at most {x^{1/u}}. From a result of Hildebrand (or the older results of de Bruijn), we know that the number {\pi(x, x^{1/u})} of {x^{1/u}}-smooth numbers less than or equal to {x} is

\displaystyle \pi(x, x^{1/u}) = x \exp( - (1+o(1)) u \log u ) \ \ \ \ \ (1)

\displaystyle = x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x} ).

Let {\pi(x^{1/u})} be the number of primes up to {x^{1/u}}. From the prime number theorem we have

\displaystyle \pi(x^{1/u}) = (1+o(1)) x^{1/u} / \log x^{1/u} \ \ \ \ \ (2)

\displaystyle = \exp( (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x} ).

To prove the lower bound on {L(x)}, which is a variant of Theorem 2. The key observation is that given any {\pi(x^{1/u})+1} {x^{1/u}}-smooth numbers {b_1,\dots,b_{\pi(x^{1/u})+1}}, some non-trivial subcollection of them will multiply to a square. This is essentially Lemma 4.2 of Bui–Pratt–Zaharescu, but for the convenience of the reader we give a full proof here. Consider the multiplicative homomorphism {f: {\bf N} \rightarrow ({\bf Z}/2{\bf Z})^{\pi(x^{1/u})}} defined by

\displaystyle f(n) := (\nu_{p_i}(n) \mod 2)_{i=1}^{\pi(x^{1/u})},

where {p_i} is the {i^{\mathrm{th}}} prime and {\nu_{p_i}(n)} is the number of times {p_i} divides {n}. The vectors {f(b_1),\dots,f(b_{\pi(x^{1/u})+1})} lie in a {\pi(x^{1/u})}-dimensional vector space over {{\bf Z}/2{\bf Z}}, and thus are linearly dependent. Thus there exists a non-trivial collection of these vectors that sums to zero, which implies that the corresponding elements of the sequence {b_1,\dots,b_{\pi(x^{1/u})+1}} multiply to a square.

From (1), (2) we can find {x \exp( - (\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x} )} sequences of {x^{1/u}}-smooth numbers {b_1 < \dots < b_{\pi(x^{1/u})+1}} in {\{1,\dots,x\}}, with each sequence being to the right of the previous sequence. By the above observation, each sequence contains some non-trivial subcollection that multiplies to a square. Concatenating all these subsequences together, we obtain a single sequence {1 \leq a_1 < \dots < a_k \leq x} with at least {x \exp( - (\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x} )} partial products multiplying to a square, giving the desired lower bound on {L(x)}.

Next, we prove the upper bound on {L(x)}. Suppose that a sequence {1 \leq a_1 < \dots < a_k \leq x} has {L(x)} partial products {a_1 \dots a_{i_l}} that are squares for some {1 \leq i_1 < \dots < i_{L(x)} \leq k}. Then we have {a_{i_l+1} \dots a_{i_{l+1}}} a square for all {0 \leq l < L(x)} (with the convention {i_0=0}). The key observation (essentially Lemma 3.4 of Bui–Pratt–Zaharescu) is that, for each {0 \leq l < L(x)}, one of the following must hold:

  • (i) At least one of the {a_{i_l+1},\dots,a_{i_{l+1}}} is {x^{1/u}}-smooth.
  • (ii) At least one of the {a_{i_l+1},\dots,a_{i_{l+1}}} is divisible by {p^2} for some prime {p>x^{1/u}}.
  • (iii) {a_{i_{l+1}} - a_{i_l+1} > x^{1/u}}.
Indeed, suppose that (i) and (ii) are not true, then one of the terms in the sequence {a_{i_l+1},\dots,a_{i_{l+1}}} is divisible by exactly one copy of {p} for some prime {p > x^{1/u}}. In order for the product {a_{i_l+1} \dots a_{i_{l+1}}} to be a square, another element of the sequence must also be divisible by the same prime; but this implies (iii).

From (1) we see that the number of {l} for which (i) occurs is at most {x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}. From the union bound we see that the number of {l} for which (ii) occurs is at most

\displaystyle \ll \sum_{p > x^{1/u}} x/p^2 \ll x^{1-1/u} = x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x}).

Finally, from the pigeonhole principle we see that the number of {l} for which (iii) occurs is also at most

\displaystyle x^{1-1/u} = x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x}).

Thus one has {L(x) \ll x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}, as desired. This completes the proof.

The upper bound arguments seem more crude to the author than the lower bound arguments, so I conjecture that the lower bound is in fact the truth: {L(x) = x\exp(-(\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}.

What are the odds, II: the Venezuelan presidential election

2 August, 2024 in math.PR, opinion | Tags: , | by | 82 comments

In a previous blog post, I discussed how, from a Bayesian perspective, learning about some new information {E} can update one’s perceived odds {{\mathbb P}(H_1) / {\mathbb P}(H_0)} about how likely an “alternative hypothesis” {H_1} is, compared to a “null hypothesis” {H_0}. The mathematical formula here is

\displaystyle \frac{{\mathbb P}(H_1|E)}{{\mathbb P}(H_0|E)} = \frac{{\mathbb P}(E|H_1)}{{\mathbb P}(E|H_0)} \frac{{\mathbb P}(H_1)}{{\mathbb P}(H_0)}. \ \ \ \ \ (1)

Thus, provided one has
  • (i) A precise formulation of the null hypothesis {H_0} and the alternative hypothesis {H_1}, and the new information {E};
  • (ii) A reasonable estimate of the prior odds {{\mathbb P}(H_1) / {\mathbb P}(H_0)} of the alternative hypothesis {H_1} being true (compared to the null hypothesis {H_0});
  • (iii) A reasonable estimate of the probability {{\mathbb P}(E|H_0)} that the event {E} would occur under the null hypothesis {H_0}; and
  • (iv) A reasonable estimate of the probability {{\mathbb P}(E|H_1)} that the event {E} would occur under the alternative hypothesis {H_1},
one can then obtain an estimate of the posterior odds {{\mathbb P}(H_1|E) / {\mathbb P}(H_0|E)} of the alternative hypothesis being true after observing the event {E}. Ingredient (iii) is usually the easiest to compute, but is only one of the key inputs required; ingredients (ii) and (iv) are far trickier, involve subjective non-mathematical considerations, and as discussed in the previous post, depend rather crucially on ingredient (i). For instance, selectively reporting some relevant information for {E}, and withholding other key information from {E}, can make the final mathematical calculation {{\mathbb P}(H_1|E) / {\mathbb P}(H_0|E)} misleading with regard to the “true” odds of {H_1} being true compared to {H_1} based on all available information, even if the calculation was technically accurate with regards to the partial information {E} provided. Also, the computation of the relative odds of two competing hypotheses {H_0} and {H_1} can become somewhat moot if there is a third hypothesis {H_2} that ends up being more plausible than either of these two hypotheses. Nevertheless, the formula (1) can still lead to useful conclusions, albeit ones that are qualified by the particular assumptions and estimates made in the analysis.

At a qualitative level, the Bayesian identity (1) is telling us the following: if an alternative hypothesis {H_1} was already somewhat plausible (so that the prior odds {{\mathbb P}(H_1) / {\mathbb P}(H_0)} was not vanishingly small), and the observed event {E} was significantly more likely to occur under hypothesis {H_1} than under {H_0}, then the hypothesis {H_1} becomes significantly more plausible (in that the posterior odds {{\mathbb P}(H_1|E) / {\mathbb P}(H_0|E)} become quite elevated). This is quite intuitive, but as discussed in the previous post, a lot hinges on how one is defining the alternative hypothesis {H_1}.

In the previous blog post, this calculation was initially illustrated with the following choices of {H_0}, {H_1}, and {E} (thus fulfilling ingredient (i)):

  • {E} was the event that the October 1, 2022 PSCO Grand Lotto in the Phillippines drew the numbers {9, 18, 27, 36, 45, 54} (that is to say, consecutive multiples if {9}), though not necessarily in that order;
  • {H_0} was the null hypothesis that the lottery was fair and the numbers were drawn uniformly at random (without replacement) from the set {\{1,\dots,55\}}; and
  • {H_1} was the alternative hypothesis that the lottery was rigged by some corrupt officials for their personal gain.
In this case, ingredient (iii) can be computed mathematically and precisely:

\displaystyle {\mathbb P}(E|H_0) = \frac{1}{\binom{55}{6}} = \frac{1}{28,989,675}. \ \ \ \ \ (2)

 And, with a not inconceivable level of cynicism about the integrity of the lottery, the prior odds (ingredient (ii)) can be argued to be non-negligible. However, ingredient (iv) was nearly impossible to estimate: indeed, as argued in that post, there is no reason to suspect that {{\mathbb P}(E|H_1)} is much larger than the tiny probability (2), and in fact it could well be smaller (since would likely be in the interest of corrupt lottery officials to not draw attention to their activities). So, despite the very small numerical value of the probability (2), this did not lead to any significant increase in the odds of the alternative hypothesis. In the previous blog post, several other variants {H'_1}, {H''_1}, {H'''_1} of the alternative hypothesis {H_1} were also discussed; the conclusion was that while some choices of alternative hypothesis could lead to elevated probabilities for ingredient (iv), they came at the cost of significantly reducing the prior odds in ingredient (ii), and so no alternative hypothesis was located which ended up being significantly more plausible than the null hypothesis {H_0} after observing the event {E}.

In this post, I would like to run the same analysis on a numerical anomaly in the recent Venezuelan presidential election of June 28, 2024. Here are the officially reported vote totals for the two main candidates, incumbent president Nicolás Maduro and opposition candidate Edmundo González, in the election:

  • Maduro: 5,150,092 votes
  • González: 4,445,978 votes
  • Other: 462,704 votes
  • Total: 10,058,774 votes.
The numerical anomaly is that if one multiplies the total number of voters {10,058,774} by the round percentages {51.2\%}, {44.2\%}, {4.6\%}, one recovers exactly the above vote counts after rounding to the nearest integer:

\displaystyle 51.2\% \times 10,058,774 = 5,150,092.288

\displaystyle 44.2\% \times 10,058,774 = 4,445,978.108

\displaystyle 4.6\% \times 10,058,774 = 462,703.604.

Let us try to apply the above Bayesian framework to this situation, bearing in mind the caveats that this analysis is only strong as the inputs supplied and assumptions made (for instance, to simplify the discussion, we will not also discuss information from exit polling, which in this case gave significantly different predictions from the percentages above).

The first step (ingredient (i)) is to formulate the null hypothesis {H_0}, the alternative hypothesis {H_1}, and the event {E}. Here is one possible choice:

  • {E} is the event that the reported vote total for Maduro, González, and Other are all equal to the nearest integer of the total number of voters, multiplied by a round percentage with one decimal point (i.e., an integer multiple of {0.1\%}).
  • {H_0} is the null hypothesis that the vote totals were reported accurately (or with only inconsequential inaccuracies).
  • {H_1} is the alternative hypothesis that the vote totals were manipulated by officials from the incumbent administration.

Ingredient (ii) – the prior odds that {H_1} is true over {H_0} – is highly subjective, and an individual’s estimation of (ii) would likely depend on, or at least be correlated with, their opinion of the current Venezulan administration. Discussion of this ingredient is therefore more political than mathematical, and I will not attempt to quantify it further here. Now we turn to (iii), the estimation of the probability {{\mathbb P}(E|H_0)} that {E} occurs given the hypothesis {H_0}. This cannot be computed exactly without a precise probabilistic model of the voting electorate, but let us make a rough order of magnitude calculation as follows. One can focus on the anomaly just for the number of votes received by Maduro and González, since if both of these counts were the nearest integer to a round percentages then just from simple subtraction the number of votes for “other” would also be forced to also be the nearest integer from a round percentage, possibly plus or minus one due to carries, so up to a factor of two or so we can ignore the latter anomaly. As a simple model, suppose that the voting percentages for Maduro and González were distributed more or less uniformly in some square {[p-\varepsilon,p+\varepsilon] \times [q-\varepsilon,q+\varepsilon]}, where {p, q} are some proportions not too close to either {0} or {1}, and {\varepsilon} is some reasonably large margin of error (the exact values of these parameters will end up not being too important, nor will the specific shape of the distribution; indeed, the shape and size of the square here only impacts the analysis through the area {(2\varepsilon)^2} of the square, and even this quantity cancels itself out in the end). Thus, the number of votes for Maduro is distributed in an interval of length about {2\varepsilon N}, where {N = 10,058,774} is the number of voters, and similarly for González, so the total number of different outcomes here is {(2\varepsilon N)^2}, and by our model we have a uniform distribution amongst all these outcomes. On the other hand, the total number of attainable round percentages for Maduro is about {(2\varepsilon) / 0.1\% = 1000 \times 2\varepsilon}, and similarly for González, so our estimate for {{\mathbb P}(E|H_0)} is

\displaystyle {\mathbb P}(E|H_0) \approx \frac{(1000 \times 2\varepsilon)^2}{(2\varepsilon N)^2} = (1000/N)^2 \approx 10^{-8}.

This looks quite unlikely! But we are not done yet, because we also need to estimate {{\mathbb P}(E|H_1)}, the probability that the event {E} would occur under the alternative hypothesis {H_1}. Here one has to be careful, because while it could happen under hypothesis {H_1} that the vote counts were manipulated to be exactly the nearest integer to a round percentage, this is not the only outcome under this hypothesis, and indeed one could argue that it would not be in the interest of an administration to generate such a striking numerical anomaly. But one can create a reasonable chain of events with which to estimate (from below) this probability by a kind of “Drake equation“. Consider the following variants of {H_1}:
  • {H'_1}: {H_1} is true, and the administration directs election officials to report vote outcomes with some explicitly preferred (round) percentages, regardless of the actual election results.
  • {H''_1}: {H'_1} is true, and the election officials dutifully generate a report by multiplying these preferred percentages by the total number {N} of voters, and rounding to the nearest integer, without any attempt to disguise their actions.
By the chain rule for conditional probability, one has a lower bound

\displaystyle {\mathbb P}(E|H_1) \geq {\mathbb P}(E, H''_1, H'_1|H_1) = {\mathbb P}(E|H''_1) {\mathbb P}(H''_1|H'_1) {\mathbb P}(H'_1|H_1).

Inserting this into (1), we obtain our final lower bound:

\displaystyle \frac{{\mathbb P}(H_1|E)}{{\mathbb P}(H_0|E)} \gtrapprox 10^8 \times {\mathbb P}(E|H''_1) {\mathbb P}(H''_1|H'_1) {\mathbb P}(H'_1|H_1) \frac{{\mathbb P}(H_1)}{{\mathbb P}(H_0)}.

This is about as far as one can get purely with mathematical analysis. Beyond this, one has to make some largely subjective estimations for each of the remaining probabilities and odds in this formula. As mentioned, the prior odds {{\mathbb P}(H_1)/{\mathbb P}(H_0)} will likely depend on the individual making this calculation, and will not be discussed further here. The remaining question then is how large the probabilities {{\mathbb P}(H'_1|H_1)}, {{\mathbb P}(H''_1|H'_1)}, and {{\mathbb P}(E|H''_1)} are. In other words:
  • If one assumes that the administration wishes to manipulate the vote totals, how likely is it a priori (i.e., without being aware of the anomaly {E}) that they would do so by explictly selecting preferred round percentages and then requesting that election officials report these percentages?
  • If one assumes that election officials are being ordered to report vote totals to reflect a preferred round percentage, how likely is it a priori that they would follow the orders without question, and performing simple rounding instead of any more sophisticated numerical manipulation?
  • If one assumes that election officials did indeed follow the orders as above, how likely is it a priori that the report would be published as is without any concerns raised by other officials or observers?
If one’s estimate of the product of these three probabilities multiplies to be significantly greater than {10^{-8}}, then we can conclude that the event {E} has indeed significantly raised the odds of some sort of voting manipulation present. The scenario described above is somewhat plausible, especially in light of the anomaly {E}, and so certainly the posterior probabilities {{\mathbb P}(H'_1|H_1,E)}, {{\mathbb P}(H''_1|H'_1,E)} seem quite large (and the posterior probability {{\mathbb P}(E|H''_1,E)} is of course equal to {1}). But it is important here to avoid confirmation bias and work only with a priori probabilities – roughly speaking, the probabilities that one would assign to such events on July 27, 2024, before knowledge of the anomaly {E} came to light. Nevertheless, even after accounting for confirmation bias, I think it is plausible that the above product of a priori probabilities is indeed significantly larger than {10^{-8}} (for instance, to assign probabilities somewhat randomly, this would be the case of each of the conditional probabilities {{\mathbb P}(H'_1|H_1)}, {{\mathbb P}(H''_1|H'_1)} and {{\mathbb P}(E|H''_1)} all exceed {1\%}), giving credence to the theory of the election report being manipulated (though it is possible that the manipulation could occur through a third hypothesis {H_2} not covered by the original two hypotheses, such as a software glitch). If one adds in additional information beyond the purely numerical anomaly {E}, such as the fact that the reported totals were not broken down further by voting district (which would be less likely under hypothesis {H_0} than hypothesis {H_1}), and that exit polls gave significantly different results from the reported totals (which is again less likely under hypothesis {H_0} than hypothesis {H_1}), the evidence for voting irregularities becomes quite significant.

One can contrast this analysis with that of the Phillipine lottery in the original post. In both cases the probability {{\mathbb P}(E|H_0)} of the observed event under the null hypothesis was extremely small. However, in the case of the Venezuelan election, there is a plausible causal chain {H_1 \implies H'_1 \implies H''_1 \implies E} that leads to an elevated probability {{\mathbb P}(E|H_1)} of the observed event under the alternative hypothesis, whereas in the case of the lottery, only extremely implausible chains could be constructed that would lead to the specific outcome of a multiples-of-9 lottery draw for that specific lottery on that specific date.

Archives