Area of a quadrilateral from the lengths of its sides

Posted on 19 January 2025 by John

Last week Heron’s formula came up in the post An Unexpected Triangle. Given the lengths of the sides of a triangle, there is a simple expression for the area of the triangle.

$A = \sqrt{s(s-a)(s-b)(s-c)}$

where the sides are a, b, and c and s is the semiperimeter, half the perimeter.

Is there an analogous formula for the area of a quadrilateral? Yes and no. If the quadrilateral is cyclic, meaning there exists a circle going through all four of its vertices, then Brahmagupta’s formula for the area of a quadrilateral is a direct generalization of Heron’s formula for the area of a triangle. If the sides of the cyclic quadrilateral are a, b, c, and d, then the area of the quadrilateral is

$A = \sqrt{(s-a)(s-b)(s-c)(s-d)}$

where again s is the semiperimeter.

But in general, the area of a quadrilateral is not determined by the length of its sides alone. There is a more general expression, Bretschneider’s formula, that expresses the area of a general quadrilateral in terms of the lengths of its sides and the sum of two opposite angles. (Either pair of opposite angles lead to the same value.)

$A = \sqrt {(s-a)(s-b)(s-c)(s-d) - abcd \, \cos^2 \left(\frac{\alpha + \gamma}{2}\right)}$

In a cyclic quadrilateral, the opposite angles α and γ add up to π, and so the cosine term drops out.

The contrast between the triangle and the quadrilateral touches on an area of math called distance geometry. At first this term may sound redundant. Isn’t geometry all about distances? Well, no. It is also about angles. Distance geometry seeks results, like Heron’s theorem, that only depend on distances.

An unexpected triangle

Posted on 18 January 2025 by John

Let J(x) be the function plotted below.

This is the Bessel function J₁, but we drop the subscript because it’s the only Bessel function we’re interested in for this post. You can think of J as a sort of damped sine.

We can create versions of J with different frequencies by multiplying the argument x by different constants. Suppose we create versions with three different frequencies — J(ax), J(bx), and J(cx) — and integrate their product. This defines a function f of the frequencies.

$f(a, b, c) = \int_0^\infty J(ax) \, J(bx) \, J(cx)\, dx$

We can evaluate the integral defining f using Sonine’s formula [1]

$f(a, b, c) = \frac{2\Delta(a, b, c)}{\pi abc}$

where Δ(a, b, c) is the area of a triangle with sides a, b, c, if such a triangle exists, and zero otherwise.

It’s amazing that this formula takes three parameters with no intrinsic geometric meaning and out pops the area of a triangle with such sides.

Numerical (mis)application

It would be ill-advised, but possible, to invert Sonine’s formula and use it to find the area of a triangle; Heron’s formula would be a far better choice. But just for fun, we’ll take the ill-advised route.

from numpy import linspace, pi, sqrt, inf
from scipy.special import j1
from scipy.integrate import quad

def heron(a, b, c):
    s = (a + b + c)/2
    return sqrt(s*(s-a)*(s-b)*(s-c))

def g(a, b, c):
    integrand = lambda x: j1(a*x) * j1(b*x) * j1(c*x)
    i, _ = quad(integrand, 0, inf, limit=500)
    return i

def area(a, b, c):
    return g(a, b, c)*pi*a*b*c/2

print(area(3,4,5), heron(3,4,5))

SciPy’s quad function has difficulty with the integration, and rightfully issues a warning. The code increases the limit parameter from the default value of 50 to 500, improving the accuracy but not eliminating the warning. The area function computes the error of a 3-4-5 triangle to be 5.9984 and the heron function computes the exact value 6.

Update: I tried the numerical integration above in Mathematica and it correctly computed the integral to 10 decimal places with no help. I suspect it is detecting the oscillatory nature of the integral and using Levin’s integration method; when I explicit set the integration to be Levin’s method, I get the same result.

Impossible triangles

You could calculate the area of a triangle from Heron’s theorem or from Sonine’s theorem. The results are identical when the parameters a, b, and c form a valid triangle. But the two approaches diverge when a, b, and c do not form a triangle. If you pass in parameters like (3, 1, 1) then Heron’s theorem gives a complex number and Sonine’s theorem yields zero.

[1] Discovered by Nikolay Yakovlevich Sonin (1849–1915). The formula is usually referred to as Sonine’s formula rather than Sonin’s formula, as far as I’ve seen. This variation is minor compared to what transliteration does to other Russian names.

Sonine’s formula is more general, extending to Bessel functions J_ν with Re(ν) > ½. I chose ν = 1 for this post because the Sonin’s formula is simplest in this case.

Dimensional analysis for gamma function values

Posted on 16 January 2025 by John

Sometimes it’s useful to apply dimensional analysis where it doesn’t belong, to imagine things having physical dimension when they don’t. This post will look at artificially injecting dimensions into equations involving factorials and related functions.

Factorials

The factorial of n is defined as the product of n terms. If each of these terms had units of length, the factorial would have units of n-dimensional volume. It occurred to me this morning that a lot of identities involving factorials make sense dimensionally if you pretend the terms in the identities have units. The expressions on both sides of an equation have the same dimension, and only terms of the same dimension are added together. This isn’t always the case, so caveat emptor.

We could also think of an nth rising power or nth falling power as an n-dimensional volume. If we do, then the dimensions in a Newton series cancel out, for example.

Dimensional analysis for factorials and related functions could make it easier to remember identities, and easier to spot errors. And it could suggest the correct form of a result before the details of the result are filled in. In other words, artificial dimensional analysis can provide the same benefits of physically meaningful dimensional analysis.

Gamma function

For integers n, Γ(n) = (n − 1)!, and so we could assign dimension n − 1 to Γ(n), and more generally assign dimension z − 1 to Γ(z) for any complex z.

Now for some examples to show this isn’t as crazy as it sounds. For starters, take the identity Γ(z + 1) = z Γ(z). We imagine the left hand side is a z-dimensional volume, and the right hand side is the product of a term with unit length and a term that represents a (z − 1) dimensional volume, so the units check out.

Next let’s take something more complicated, the Legendre duplication formula:

$\Gamma (z)\Gamma \left(z+\frac{1}{2}\right)=2^{1-2z}\sqrt{\pi} \; \Gamma (2z)$
The left hand side has dimension (z − 1) + (z − ½) = 2z − ½. The right hand side has dimension 2z − 1, apparently contradicting our dimensional analysis scheme. But √π = Γ(½), and if we rewrite √π as Γ(½) in the equation above, both sides have dimension 2z − ½. The dimensions in other identities, like the reflection formula, also balance when you replace π with Γ(½)².

Hypergeometric functions

The hypergeometric function F(a, b; c; z) is defined by its power series representation. If we assign dimensions to the coefficients in the series as we’ve done here, then the numerator and denominator of each term have the same dimensions, and so the hypergeometric function should be dimensionless in our sense. This implies we should expect that identities for hypergeometric functions to be dimensionless as well. And indeed they are. I’ll give two examples.

First, let’s look at Gauss’ summation identity

$F (a,b;c;1)= \frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)}$

provided the real part of c is greater than the real part of a + b. Notice that the numerator and denominator both have dimension 2c − a − b − 2.

Next, let’s look at Kummer’s identity

$F (a,b;1+a-b;-1)= \frac{\Gamma(1+a-b)\Gamma(1+\tfrac12a)}{\Gamma(1+a)\Gamma(1+\tfrac12a-b)}$

Both the numerator and denominator have dimension 3a/2 − b.

Finally, let’s look at a more complicated formula.

$\begin{align*} F(a, b; c; z) &= \frac{\Gamma(c) \Gamma(b-a)}{\Gamma(b) \Gamma(c-a)} \,(-z)^{-a\phantom{b}} F\left(a, 1-c+a; 1-b+a; \frac{1}{z}\right) \\ &+ \frac{\Gamma(c) \Gamma(a-b)}{\Gamma(a) \Gamma(c-b)} \,(-z)^{-b\phantom{a}} F\left(\,b, 1-c+b; 1-a+b; \,\frac{1}{z}\right) \\ \end{align*}$

In both the terms involving gamma functions, the dimensions of the numerator and denominator cancel out.

Falling power analog of binomial theorem

Posted on 15 January 2025 by John

Yesterday I wrote about how the right notation could make Newton’s interpolation theorem much easier to remember, revealing it as an analog of Taylor series. This post will do something similar for the binomial theorem.

Let’s start with the following identity.

It’s not clear that this is true, or how one might generalize it. But if we rewrite the equation using falling power notation we have

$(x + y)^{\underline{3}} = x^{\underline{3}} + 3x^{\underline{2}} y^{\underline{1}} + 3x^{\underline{1}}y^{\underline{2}} + y^{\underline{3}}$

which looks a lot like the binomial theorem. In fact it is the case n = 3 of the Chu-Vandermonde theorem which says

$(x + y)^{\underline{n}} = \sum_{k=0}^n \binom{n}{k} x^{\underline{n-k}} y^{\underline{k}}$

Viewed purely visually, this is the binomial theorem with little lines under each exponent.

Incidentally, the analogous theorem holds for rising powers. Just change all the lines under the exponents to lines on top of the exponents.

Discrete Taylor series

Posted on 14 January 2025 by John

Newton’s interpolation formula looks awfully complicated until you introduce the right notation. With the right notation, it looks like a Taylor series. Not only is this notation simpler and more memorable, it also suggests extensions.

The notation we need comes in two parts. First, we need the forward difference operator Δ defined by

$\Delta f(x) = f(x+1) - f(x)$

and its extension Δ^k defined by applying Δ to a function k times.

The other piece of notation we need is falling powers, denoted with a little bar under the exponent:

$x^{\underline{k}} = x(x-1)(x-2) \cdots (x - k + 1)$

The Δ operator is meant to resemble the differential operator D and falling powers are meant to resemble ordinary powers. With this notation, Newton’s interpolation formula based at a

$f(x) = \sum_{k=0}^\infty \frac{\Delta^k f(a)}{k!} (x - a)^{\underline{k}}$

looks analogous to Taylor’s formula for a power series based at a

$f(x) = \sum_{k=0}^\infty \frac{D^k f(a)}{k!} (x - a)^k.$

Newton’s formula applies to polynomials, and the infinite sum is actually a finite sum because Δ^k f(a) is 0 for all k beyond some point.

Newton’s formula is a discrete analog of Taylor’s formula because it only uses the values of f at discrete points, i.e. at the integers (shifted by a) and only involves finite operations: finite differences do not involve limits.

Convergence

As I mentioned on @AlgebraFact this morning,

It’s often useful to write a finite series as an infinite series with a finite number of non-zero coefficients.

This eliminates the need to explicitly track the number of terms, and may suggest what to do next.

Writing Newton’s formula as an infinite series keeps us from having to write down one version for linear interpolation, another version for quadratic interpolation, another for cubic interpolation, etc. (It’s a good exercise to write out these special cases when you’re new to the topic, but then remember the infinite series version going forward.)

As for suggesting what to do next, it’s natural to explore what happens if the infinite series really is infinite, i.e. if f is not a polynomial. Under what circumstances does the series converge? If it does converge to something, does it necessarily converge to f(x) at each x?

The example f(x) = sin(πx) shows that Newton’s theorem can’t always hold, because for this function, with a = 0, the series on right hand side of Newton’s theorem is identically zero because all the Δ^k terms are zero. But Carlson’s theorem [1] essentially says that for an entire function that grows slower than sin(πx) along the imaginary axis the series in Newton’s theorem converges to f.

Saying that a function is “entire” means that it is analytic in the entire complex plane. This means that Taylor’s series above has to converge everywhere in order for Newton’s series to converge [2].

[1] Carlson with no e. Not to be confused with Carleson’s theorem on the convergence of Fourier series.

[2] Carlson’s original theorem requires f to be entire. Later refinements show that it’s sufficient for f to be analytic in the open right half plane and continuous on the closed right half plane.

RSA security in light of news

Posted on 9 January 2025 by John

A recent article reported on the successful factoring of a 512-bit RSA key. The process took $8 worth of rented computing power. What does that say about the security of RSA encryption?

The following Python function estimates the computation steps required to factor a number b bits long using the best known algorithm. We’re going to take a ratio of two such estimates, so proportionality constants will cancel.

def f(b):
    logn = b*log(2)
    return exp((8/3)**(2/3) * logn**(1/3) * (log(logn))**(2/3))

The minimum recommended RSA key size is 2048 bits. The cost ratio for factoring a 2048 bit key to a 512 bit key is f(2048) / f(512), which is on the order of 10¹⁶. So factoring a 2048-bit key would take 80 quadrillion dollars.

This is sort of a back-of-the-envelope estimate. There things it doesn’t take into account. If a sophisticated and highly determined entity wanted to factor a 2048 number, they could probably do so for less than 80 quadrillion dollars. But it’s safe to say that the people who factored the 512 bit key are unlikely to factor a 2048 bit key by the same approach.

Carnival of Mathematics 235

Posted on 2 January 2025 by John

A blog carnival is a way to discover new blogs. Writers on a given topic, such as math, take turns hosting the carnival, featuring recent posts from various writers. Blog carnivals were once much more common, but most have faded away.

The Carnival of Mathematics, however, is one of the oldest carnivals and still active, as evidenced by the fact that this is the 235th edition of the Carnival.

I’ve hosted the Carnival here several times. The first time was #50 and the most recent was #222.

The Aperiodical is a sort of meta-host for the Carnival: you can find past and future hosts by visiting this site.

Number trivia

It is traditional for the nth edition of the Carnival of Mathematics to begin with trivia about the number n.

According to Number Gossip, “235 is the smallest number whose first two digits are distinct primes such that their sum equals the third digit.”

235 is a centered triangular number. The figure below contains 235 dots.

235 is a semiprime, i.e. the product of two prime numbers, in this case 5 and 47. There is a theorem that says there is only one group of order pq if p and q are prime, p > q, and q is not a factor of p − 1, and so there is only one group with 235 elements, namely the direct sum of the cyclic groups of order 5 and 47.

Post submissions

There were two links to Terence Tao‘s site this time. The first was an announcement for the AI for Math fund. The second was Tao’s brief notes on quaternions and spherical trigonometry.

We have a link from a post by Mike Croucher on solving higher-order ODEs in MATLAB. As with many software environments, MATLAB does not directly support higher-order ODEs but does support systems of first-order ODEs, and you can always convert the former to the latter. Croucher shows how to do this conversion, first by hand and then by using MATLAB’s symbolic calculation features.

Ionna Georgiu has posted a collection of videos on a variety of topics, including evidence of what we now call the Pythagorean theorem a millennium before Pythagoras.

Someone submitted to a Xena Project post by Kevin Buzzard on formalizing Fermat’s Last Theorem (FLT) in Lean. One line that struct me from the article was “We’re not formalising the old-fashioned 1990s proof of FLT. Since then, work of many people … led to the proof being generalised and simplified …” So in one generation, Wiles’ proof has gone from ground-breaking to old-fashioned.

Sophie Huiberts made a video entitled Open Problems and Diet Problems about linear programming, optimizing a linear objective function subject to linear constraints. The simplex method for solving such optimization problems performs much better in practice than in worst-case theory. In practice the time required to execute the algorithm is proportional to the size of the problem, but one can construct artificial problems for which the time required grows exponentially with the problem size. Huiberts looks at a probabilistic explanation of why the simplex method works so well, but concludes that the explanation is not satisfying.

Up to isomorphism

Posted on 1 January 2025 by John

The previous post showed that there are 10 Abelian groups that have 2025 elements. Implicitly that means there are 10 Abelian groups up to isomorphism, i.e. groups that are not in some sense “the same” even if they look different.

Sometimes it is clear what we mean by “the same” and there’s no need to explicitly say “up to isomorphism” and doing so would be pedantic. Other times it helps to be more explicit.

In some context you want to distinguish isomorphic as different objects. This is fine, but it means that you have some notion of “different” that is more strict than “not isomorphic.” For example, the x-axis and the y-axis are different subsets of the plane, but they’re isomorphic as 1-dimensional vector spaces.

Abelian groups

There is a theorem that says ℤ_mn, the group of integers mod mn, is isomorphic to the direct sum ℤ_m ⊕ ℤ_n if and only if m and n are relatively prime. This means, for example, that ℤ₁₅ and ℤ₃ ⊕ ℤ₅ are isomorphic, but ℤ₉ and ℤ₃ ⊕ ℤ₃ are not.

Because of this theorem it’s possible to come up with a list of Abelian groups of order 2025 that looks different from the list in the previous post but it actually the same, where “same” means isomorphic.

In the previous post we listed direct sums of groups where each group was a cyclic group of some prime power order:

ℤ₈₁ ⊕ ℤ₂₅
ℤ₈₁ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₂₇ ⊕ ℤ₃ ⊕ ℤ₂₅
ℤ₂₇ ⊕ ℤ₃ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₉ ⊕ ℤ₉ ⊕ ℤ₂₅
ℤ₉ ⊕ ℤ₉ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₉ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₂₅
ℤ₉ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₂₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₅ ⊕ ℤ₅

We could rewrite this list as follows by combining group factors of relatively prime orders:

ℤ₂₀₂₅
ℤ₅ ⊕ ℤ₄₀₅
ℤ₃ ⊕ ℤ₆₇₅
ℤ₁₅ ⊕ ℤ₁₃₅
ℤ₉ ⊕ ℤ₂₂₅
ℤ₄₅ ⊕ ℤ₄₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₂₉₅
ℤ₃ ⊕ ℤ₁₅ ⊕ ℤ₄₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₇₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₁₅ ⊕ ℤ₁₅

This listing follows a different convention, namely that the order of each group is a factor of the order of the next.

Abelian groups of order 2025

Posted on 1 January 2025 by John

Every finite Abelian group can be written as the direct sum of cyclic groups of prime power order.

To find the number of Abelian groups of order 2025 we have to find the number of ways to partition the factors of 2025 into prime powers.

Now 2025 = 3⁴ × 5².

We can partition 3⁴ into prime powers 5 ways:

3⁴
3³ × 3
3² × 3²
3² × 3 × 3
3 × 3 × 3 × 3

And we can partition 5² two ways:

5²
5 × 5

A couple of notes here. First, we only consider positive powers. Second, two partitions are considered the same if they consist of the same factors in a different order. For example, 3 × 3 × 3²and 3²× 3 × 3 are considered to be the same partition.

It follows that we can partition 2025 into prime powers 10 ways: we choose one of the five ways to partition 3⁴ and one of the two ways to partition 5². Here are all the Abelian groups of order 2025:

ℤ₈₁ ⊕ ℤ₂₅
ℤ₈₁ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₂₇ ⊕ ℤ₃ ⊕ ℤ₂₅
ℤ₂₇ ⊕ ℤ₃ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₉ ⊕ ℤ₉ ⊕ ℤ₂₅
ℤ₉ ⊕ ℤ₉ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₉ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₂₅
ℤ₉ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₅ ⊕ ℤ₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₂₅
ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₃ ⊕ ℤ₅ ⊕ ℤ₅

Given a prime number q, there are as many ways to partition q^k as the product of positive prime powers as there are ways to partition k into the sum of positive integers, denoted p(k). What we have shown above is that the number of Abelian groups of order 3⁴ 5² equals p(4) p(2).

In general, to find the number of Abelian groups of order n, factor n into prime powers, then multiply the partition numbers of the exponents in the factorization.

Details of generating primes for cryptography

Posted on 31 December 2024 by John

RSA public key cryptography begins by finding a couple large primes. You essentially do this by testing random numbers until you find primes, but not quite.

Filippo Valsorda just posted a good article on this.

Suppose you’re looking for a 1024-bit prime number. You generate random 1024-bit numbers and then test until you find one that’s prime. You can immediately make this process twice as fast by setting the last bit to 1: it would be wasteful to generate a new number every time you happened to draw an even number.

A little less obvious is that it’s common to set the top bit as well. When you’re generating a number between 0 and 2¹⁰²⁴ − 1, it’s possible that you could generate a small number. It’s possible that you generate a very small number, like 59, but extremely unlikely. But it’s not so unlikely that you’d generate a number on the order of 2¹⁰²⁰, for example. By setting the top bit, you know you’re generating a number between 2¹⁰²³ and 2¹⁰²⁴.

Most composite numbers have small factors, so you check for divisibility by 3, 5, 7 etc. before running more time-consuming tests. Probabilistic tests are far more efficient than deterministic tests, so in practice everyone uses probable primes in RSA. For details of how you apply these tests, and how many tests to run, see Filippo Valsorda’s article.

Should you be concerned about setting the top bit of prime candidates? There are naive and sophisticated reasons not work worry, and an intermediate reason to at least think about it.

The naive response is that you’re just losing one bit of randomness. How much could that hurt? But in other contexts, such as losing one bit of randomness in an AES key, people do worry about such losses.

The bits in the prime factors of an RSA modulus do not correspond directly to bits of security. A 2048-bit modulus, the product of two 1024-bit primes, has about 112 bits of security. (See NIST SP 800-57.) You could set several bits in your prime factors before losing a bit of security. If this bothers you, move up to using a 3072-bit modulus rather than worrying that you 2048-bit modulus is in a sense a 2046-bit modulus.

Math

Area of a quadrilateral from the lengths of its sides

Related posts

An unexpected triangle

Numerical (mis)application

Impossible triangles

Related posts

Dimensional analysis for gamma function values

Factorials

Gamma function

Hypergeometric functions

Falling power analog of binomial theorem

Discrete Taylor series

Convergence

Related posts

RSA security in light of news

Carnival of Mathematics 235

Number trivia

Post submissions

Details of generating primes for cryptography

More cryptography posts