2025-08-02 20:00:14
Yesterday’s post mentioned Tweedledum and Tweedledee, a pair of elliptic curves named after characters in Lewis Carroll’s Through the Looking Glass.
Zcash uses a very similar pair of elliptic curves for zero-knowledge proofs: Pallas and Vesta. One named after a Greek goddess associated with war, and one named after a Roman goddess associated with home and hearth. (Zcash used the Jubjub curve, also mentioned yesterday, though not in the most recent release.)
The curves Pallas and Vesta are collectively known as the “pasta” curves, pasta being a portmanteau of pallas and vesta.
pa(llas ve)sta
Tweedledum, Tweedledee, Pallas, and Vesta all have the equation
y² = x³ + 5
over different prime-order fields.
The number of elements in Tweedledum’s field equals the number of elements in Tweedledee’s elliptic curve, and vice versa. The same relationship holds between Pallas and Vesta. And all four curves have roughly 2254 points.
If p is the size of Tweedledum’s field (and Tweedledee’s curve), and q is the size of Tweedledee’s field (and Tweedledum’s curve),
p = 2254 + 4707489545178046908921067385359695873
q = 2254 + 4707489544292117082687961190295928833
If p is the size of Pallas’ field (and Vesta’s curve), and q is the size of Vesta’s field (and Pallas’ curve),
p = 2254 + 45560315531419706090280762371685220353
q = 2254 + 45560315531506369815346746415080538113
2025-08-02 01:33:28
Elliptic curves are often used in cryptography, and in particular they are used in zero-knowledge proofs (ZKP). Cryptocurrencies such as Zcash use ZKP to protect the privacy of users.
Several of the elliptic curves used in ZKP have whimsical names taken from characters by Lewis Carroll. This post will look at these five elliptic curves:
Charles Dodgson was a mathematician, and perhaps there’s some connection from his mathematical work to elliptic curves and ZKP, the connection explored here is with his literary works written under the name Lewis Carroll.
The first three curves—Jubjub, Baby Jubjub, and Bandersnatch—all get their name from Lewis Carroll’s poem Jabberwocky.
“Beware the Jabberwock, my son!
The jaws that bite, the claws that catch!
Beware the Jubjub bird, and shun
The frumious Bandersnatch!”
These curves all have a have a twisted Edwards curve form and a Montgomery curve form, just like the relationship between Ed25519 and Curve25519 that I wrote about a few days ago.
As its name suggests, the Baby Jubjub elliptic curve is related to the Jubjub curve but smaller.
Bandersnatch is similar to Jubjub, but arithmetic over this curve can be implemented more efficiently.
The last two curves—Tweedledum and Tweedledee—take their names from Through the Looking Glass.
And as their names suggest, Tweedledum and Tweedledee and very closely related. Both have the equation
y² = x³ + 5
but over different fields. Tweedledum is defined over the integers mod p and has q elements. Tweedledee is defined over the integers mod q and has p elements. (Mind your ps and qs!)
Here
p = 2254 + 4707489545178046908921067385359695873
q = 2254 + 4707489544292117082687961190295928833
2025-08-01 07:51:59
Iconjack posted on X today
(Possibly) surprising fact: a regular dodecahedron is rounder than a regular icosahedron.
You might reasonably suppose that having more sides would result in a rounder figure, so a figure with 20 sides should be rounder than a figure with 12 sides. But it’s the other way around.
Here’s one way to see the statement above. In a dodecahedron, three pentagons come together at each vertex. The interior angles of a pentagon have 108°. If you were to take the three pentagons, cut a slit long one slide, and push them flat on to a plane, there would be a gap of
360° − 3 × 108° = 36°.
This gap is known as the angle defect and is the discrete analog of curvature.
In an icosahedron you have five triangles coming together at a point. So if you were to push the five triangles at a vertex down to a point, there would be a gap (angle defect) of
360° − 5 × 60° = 60°.
The larger angle defect means the shape is less round at a vertex.
For completeness, the angle defect of a cube is 90°. For an octahedron it’s 240° and for a tetrahedron it’s 270°.
Angle defect is the standard way to measure how round a polyhedron is. It focuses on how faces fit together at a vertex. But we could instead focus on how faces fit together at an edge. The angle between two adjacent faces is the dihedral angle.
The faces of an icosahedron come meet at an angle of approximately 138.19°. For a dodecahedron, the angle is 116.57°. So the icosahedron is rounder in the sense that the faces come together at an angle closer to 180°.
The dihedral angles for the octahedron, cube, and tetrahedron are 109.47°, 90°, and 70.53°.
2025-08-01 01:21:15
Define B = {0, 1} and a Boolean function fp: BN → B where p is a Boolean parameter vector in Bn. Consider that fp(x) can be represented as a Boolean expression whose variables are the entries of vectors p and x. Assume that c is the cost of computing fp(x) measured in some way, for example, the number of operator evaluations based on some complete set of Boolean operators. Then, given y in B and x in BN, the cost to solve the equation fp(x) = y for satisfying y has cost c2n, using the most naïve brute force search.
For 3SAT solving, a much better worst case bound is known, namely O(1.307n), see here, for a related discussion see here. For the inexactly-defined class of “industrial problems,” performance in practice is often much better; for a discussion see here.
Now consider a set of Boolean feature vectors xi and labels yi. for i in {1, …, d}. One can now solve fp(xi) = yi for all i. Since the number of unknown variables to be solved for is unchanged, the naïve bound on computational cost is cd2n, scaling linearly in the number of data values d. Note this is tractable if the phenomenon in question can be modeled by a small number of logical parameters n.
In practice, one generally does not solve a machine learning problem exactly but approximately, minimizing a loss function. One can use the AtLeast operator in a SAT solver like Z3 to require that fp(xi) = yi be satisfied for at least K values of i, for some K. One can then find the maximal such K by performing bisection on K, requiring log2(d) such SAT solves. On exact solvers for this problem see also here.
The AtLeast operator can be implemented by either binary adder / totalizer encoding (Bailleux and Boufkhad 2003), sequential counter encoding (Sinz 2005), or Batcher sorting network approach (Abío et al. 2013). Unfortunately, all these methods require adding significant numbers of auxiliary variables, adversely affecting the naïve complexity bound. However, one can hope that performance is much better than this bound for industrial problems, as is often the case in practice. Furthermore, randomized approximation algorithms known to run in polynomial time can provably find assignments that satisfy a guaranteed fraction (e.g., 3/4 or more) of the maximum number of satisfiable Boolean constraints (see for example here, here, here and here). This might serve as a proxy for exactly solving for the optimizer.
If the problem instead has Boolean expressions with embedded linear inequality predicates on integer variables of bounded range, one could apply SMT solver methods directly using the ideas described above, or convert the problem to a SAT problem and apply the above methods directly.
The idea of using SAT solvers for machine learning in the way described here goes back to (Kamath et al. 1992). The method is described with an example in Donald Knuth’s TAOCP fascicle on Satisfiability, section on Learning a Boolean function.
The post Machine learning by satisfiability solving first appeared on John D. Cook.2025-08-01 00:12:39
If three circles are all tangent to each other, you can find two more circles that are tangent to all three, and the equation for finding these new circles is remarkably elegant. This is Descartes’ theorem.
To illustrate Descartes’ theorem, we first need three mutually tangent circles. Drawing two mutually tangent circles is easy. We choose our coordinate system so that the first circle is centered at the origin
O1 = (x1, y1) = (0, 0)
and the center of the second circle is on the x-axis. If the two circles have radii r1 and r2, then the center of the second circle is at
O2 = (x2, y2) = (r1 + r2, 0).
I’ve assumed that the second circle is outside the first. You could have a tangent circle inside another circle, but to illustrate Descartes’ theorem we need circles that are externally tangent.
Now we pick the radius of the third circle to be r3. The center of this circle must belong to a circle of radius r1 + r3 centered at O1 and to a circle of radius r2 + r3 centered at O2. I went over finding the point(s) of intersection of two circles here.
For illustration I chose r1 = 2, r2 = 1, and r3 = 2.8. Using the code from the aforementioned post I found
(x3, y3) = (2.93333333 3.79941516)
Here’s a plot.
Now we’re in a position to state and illustrate Descartes’ theorem. The theorem is most easily stated in terms of signed curvatures.
The curvature of a circle of radius r is 1/r. Big circles have small curvature and small circles have big curvature.
For Descartes’ theorem we need to use signed curvatures, taking the sign to be positive if circles are externally tangent and negative if the circles are internally tangent. The signed curvatures of our three circles are positive, that is
ki = 1/ri
for i = 1, 2, and 3. But Descartes’ theorem will give us two circles, one between the three given circles and one surrounding them, corresponding to a positive and negative solution for k4.
Now we can state Descartes’ theorem [1]:
(k1 + k2 + k3 + k4)² = 2(k1² + k2² + k3² + k4²)
This gives us a quadratic equation for k4 with two solutions:
k4 = k1 + k2 + k3 ±2(k1k2 + k2k3 + k1k3)½.
Now we know the radii of our tangent circles, but not the centers. For this we view the circles as living in the complex plane with centers zi. Then the centers satisfy a theorem analogous to the one satisfied by the curvatures.
(k1z1 + k2z2 + k3z3 + k4z4)² = 2(k1²z1² + k2²z2² + k3²z3² + k4²z4²)
In other words, the curvature-center products satisfy the same equation as the curvatures.
I’m unclear on the history here, but I don’t believe Descartes had a formula for the centers of the circles. He certainly did not have the formula above using complex numbers [2].
Here’s a plot of the two circles guaranteed by Descartes’ theorem.
[1] The Soddy-Gossett theorem generalizes Descartes theorem to the case of n + 2 spheres in ℝn. The square of the sums of the curvatures equals n the sum of the curvatures squared.
[2] Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks. Beyond the Descartes circle theorem. https://arxiv.org/abs/math/0101066v1
The post Finding tangent circles first appeared on John D. Cook.2025-07-31 09:53:19
A Pythagorean triangle is a right triangle with integer sides. A primitive Pythagorean triangle is one in which the sides have no factor in common. For example a triangle with sides (30, 40, 50) is a Pythagorean triangle but not a primitive Pythagorean triangle.
It is possible for two primitive Pythagorean triangles to have the same area. The smallest example is (20, 21, 29) and (12, 35, 37). Both have area 210.
It’s also possible for three primitive Pythagorean triangles to have the same area, but the smallest example is much larger. The triangles (4485, 5852, 7373), (1380, 19019, 19069), and (3059, 8580, 9109) all have area 13123110, discovered by C. L. Shedd in 1945.
Nobody has found an example of four primitive Pythagorean triangles having the same area. I don’t know whether it’s been settled whether such triangles exist. But it has been proven that if they exist, they have area greater than 9.3 × 1024. See OEIS A093536.
Incidentally, the triangle (20, 21, 29) came up in the post Do perimeter and area determine a triangle? from February of this year.
The post Primitive Pythagorean triangles with the same area first appeared on John D. Cook.
