Month: June 2018

Gauss’ golden theorem: quadratic reciprocity

Posted on by John

Suppose you have an odd prime p and an integer a, with a not a multiple of p. Does a have a square root mod p? That is, does there exist an integer x such that x² is congruent to a mod p? Half the time the answer is yes, and half the time it’s no. (We will remove the restriction that p is prime near the end of the post.)

In principle it’s easy to tell whether a has a square root: square all the integers from 1 to p − 1 and see whether one of them is congruent to a. For example, let p = 7. Square the numbers 1 through 6 and take the remainders by 7. You get 1, 4, 2, 2, 4, 1. So the numbers 1, 2, and 4 have square roots mod 7, and the numbers 3, 5, and 6 do not. In application, p might be very large, and so such brute force isn’t practical.

Legendre symbols

Before we go any further it will help to introduce some notation. The Legendre symbol

\left(\frac{a}{p}\right)

looks like a fraction, but it’s not. As we’ll see, it behaves something like a fraction, which was the motivation for the notation. But the symbol is defined to be 0 if a is a multiple of p, 1 if a has a square root mod p, and −1 otherwise.

One key fact is for any numbers m and n that are not multiples of p,

\left(\frac{m}{p}\right) \left(\frac{n}{p}\right) = \left(\frac{mn}{p}\right)

So Legendre symbols multiply like fractions on top but not on bottom. This tells us that we can tell whether a has a square root mod p by factoring a and determining whether each of its factors has a square root. For example, suppose we want to know whether 108 has a square root modulo some prime p. Since 108 = 2² 3³ the question boils down to whether 3 has a square root mod p, because obviously 2² 3² has a square root, namely 2×3 = 6.

Quadratic reciprocity

The most important result we need is Gauss’ quadratic reciprocity theorem, what he called his golden theorem. Gauss published six proofs of this theorem, and left two more proofs unpublished.

One thing you can do with a fraction is take its reciprocal, and the quadratic reciprocity theorem takes the “reciprocal” of the Legendre symbol. The quadratic reciprocity theorem says that if p and q are odd primes, then

\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}

Algorithm for computing Legendre symbols

Suppose p < q. The quadratic reciprocity theorem says we can reduce the problem of determining whether p has a square root mod q to the opposite problem, determining whether q has a square root mod p. Why is that progress? Because we can reduce q mod p, and so now we’re dealing with smaller numbers. For example, quadratic reciprocity tells us that 7 has a square root mod 61 if and only if 61 has a square root mod 7. But 61 is congruent to 5 mod 7, so we’ve reduced the question to whether 5 has a square root mod 7, and we know from above that it does not.

You can repeatedly apply the techniques of factoring the top of the Legendre symbol and applying quadratic reciprocity to steadily decrease the size of the numbers you’re dealing with until you get either a 1 or a 2 on top. (Why not apply quadratic reciprocity one more time when you get a 2 on top? Because the theorem applies to odd primes.)

If you get a 1 on top, the answer is obvious: 1 has a square root, namely itself, modulo anything. If you get a 2 on top, you need the result

\left(\frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}}

Jacobi symbols

You might think you could compute the Legendre symbol in Mathematica with a function called LegendreSymbol, but there’s no such function. Instead, you call JacobiSymbol. The Jacobi symbol is a generalization of the Legendre symbol, using the same notation but allowing the “denominator” to be any odd positive number. As before the symbol is defined to be 1 if the top has a square root modulo the bottom, and -1 otherwise.

If m has prime factors pi with exponents ei, then the Jacobi symbol can be computed by

\left(\frac{n}{m}\right) = \prod \left(\frac{n}{p_i} \right )^{e_i}

Technically the symbol on the left is a Jacobi symbol and the symbols on the right are Legendre symbols. But the distinction doesn’t matter because when m is an odd prime, the Jacobi symbol equals the Legendre symbol.

In Python, you can compute Legendre symbols with sympy.ntheory.legendre_symbol and Jacobi symbols with sympy.ntheory.jacobi_symbol.

Finding square roots

So far we’ve described how to determine whether a number has a square root mod m where m is odd. Once you know a square root exists, how do you find it?

These notes show how to solve quadratic congruences, whether m is odd or not.

Does computer science help you program?

Posted on by John

The relationship between programming and computer science is hard to describe. Purists will say that computer science has nothing to do with programming, but that goes too far.

Computer science is about more than programming, but it’s is all motivated by getting computers to do things. With few exceptions. students major in computer science in college with the intention of becoming programmers.

I asked on Twitter yesterday how helpful people found computer science in writing software.

In a follow up tweet I said “For this poll, basic CS would be data structures and analysis of algorithms. Advanced CS is anything after that.”

So about a quarter didn’t find computer science useful, but the rest either expected it to be useful or at least found the basic theory useful.

I suspect some of those who said they haven’t found (advanced) CS theory useful don’t know (advanced) CS theory. This isn’t a knock on them. It’s only the observation that you can’t use what you aren’t at least aware of. In fact, you may need to know something quite well before you can recognize an opportunity to use it. (More on that here.)

Many programmers are in jobs where they don’t have much need for computer science theory. I thought about making that a possible choice, something like “No, but I wish I were in a job that could use more theory.” Unfortunately Twitter survey responses have to be fairly short.

Of course this isn’t a scientific survey. (Even supposedly scientific surveys aren’t that great.) People who follow the CompSciFact twitter account have an interest in computer science. Maybe people who had strong feelings about CS, such as resentment for having to study something they didn’t want to or excitement for being able to use something they find interesting, were more likely to answer the question.

 

Linear regression and planet spacing

Posted on by John

A while back I wrote about how planets are evenly spaced on a log scale. I made a bunch of plots, based on our solar system and the extrasolar systems with the most planets, and said noted that they’re all roughly straight lines. Here’s the plot for our solar system, including dwarf planets, with distance on a logarithmic scale.

Distances in our solar system including planets and dwarf planets

This post is a quick follow up to that one. You can quantify how straight the lines are by using linear regression and comparing the actual spacing with the spacing given by the best straight line. Here I’m regressing the log of the distance of each planet from its star on the planet’s ordinal position.

NB: I am only using regression output as a measure of goodness of fit. I am not interpreting anything as a probability.

|-----------+-----------+----------+-----------|
| System    | Adjusted  | Slope    | Intercept |
|           | R-squared | p-value  | p-value   |
|-----------+-----------+----------+-----------|
| home      |    0.9943 | 1.29e-11 |  2.84e-08 |
| kepler90  |    0.9571 | 1.58e-05 |  1.29e-06 |
| hd10180   |    0.9655 | 1.41e-06 |  2.03e-07 |
| hr8832    |    0.9444 | 1.60e-04 |  5.57e-05 |
| trappist1 |    0.9932 | 8.30e-07 |  1.09e-09 |
| kepler11  |    0.9530 | 5.38e-04 |  2.00e-05 |
| hd40307   |    0.9691 | 2.30e-04 |  1.77e-05 |
| kepler20  |    0.9939 | 8.83e-06 |  3.36e-07 |
| hd34445   |    0.9679 | 2.50e-04 |  4.64e-04 |
|-----------+-----------+----------+-----------|

R² is typically interpreted as how much of the variation in the data is explained by the model. In the table above, the smallest value of R² is 94%.

p-values are commonly, and wrongly, understood to be the probability of a model assumption being incorrect. As I said above, I’m completely avoiding any interpretation of p-values as the probability of anything, only noting that small values are consistent with a good fit.

Journals commonly, and wrongly, are willing to assume that anything with a p-value less than 0.05 is probably true. Some are saying the cutoff should be 0.005. There are problems with using any p-value cutoff, but I don’t want to get into here. I’m only saying that small p-values are typically seen as evidence that a model fits, and the values above are orders of magnitude smaller than what journals consider acceptable evidence.

When I posted my article about planet spacing I got some heated feedback saying that this isn’t exact, that it’s unscientific, etc. I thought that was strange. I never said it was exact, only that it was a rough pattern. And although it’s not exact, it would be hard to find empirical studies of anything with such a good fit. If you held economics or psychology, for example, to the same standards of evidence, there wouldn’t be much left.

This pattern is known as the Titius-Bode law. I stumbled on it by making some plots. I assumed from the beginning that someone else must have done the same exercise and that the pattern had a name, but I didn’t know that name until later.

Someone sent me a paper that analyzes the data on extrasolar planets and Bode’s law, something much more sophisticated than the crude sketch above, but unfortunately I can’t find it this morning. I don’t recall what they did. Maybe they fit a hierarchical model where each system has its own slope and intercept.

One criticism has been that by regressing against planet order, you automatically get a monotone function. That’s true, but you do get a much better fit on a log scale than on a linear scale in any case. You might look at just the relative planet spacings without reference to order.

Objectives and constraints

Posted on by John

Objectives and constraints are symmetrical in a mathematical sense but are asymmetrical in a psychological sense. By taking dual formulations, you can reverse the mathematical role of objectives and constraints, but in application objectives are more obvious than constraints.

In the question “What is the minimum value of x² over the interval [1, 5]?” the function f(x) = x² is the objective function and 1 ≤ x ≤ 5 is the constraint. If someone says the minimum is 0, they’ve minimized the objective function but ignored the constraint. This is clear in a such a simple problem, but failure to consider constraints can be much more subtle.

Objectives tend to be easily quantifiable—maximize profit, minimize energy consumption, etc.— but constraints tend to be less quantifiable—the solution has to be testable and maintainable, has to be legal, has to be something people will buy or vote for, etc.

When children ask “Why don’t you just …” it’s because they see a way to improve some objective, but the “just” part shows that they are either completely unaware of a relevant constraint or are unaware of how difficult it would be to overcome the constraint. As you mature, you become aware of more constraints. You realize that things that seem grossly subopitmal are actually close to optimal when you consider the necessary constraints. There may be room for improvement, but not as much as you imagined and at a higher cost.

Big opportunities open up when constraints change. Maybe an idea was abandoned because it would require more calculation than anyone could carry out by hand, and now’s the time to revisit it. Or maybe an idea was never developed because it would require instantaneous communication between people at multiple points on the globe. No problem now.

In both the examples above, a constraint was relaxed: computation and communication have gotten far less expensive. Increased constraints create opportunities as well. When the price of something goes up, its alternatives become more economical by comparison. Whether an oil field is worth developing, for example, depends on the current price of oil.

If I ask “Why hasn’t someone done this before?” I’m skeptical if the answer is “Because I’m smarter than everyone else who has tried.” But if the answer is “Because constraints have changed” then I’m much more receptive.

Related post: Boundary conditions are the hard part

Surprising curves with sine and sn

Posted on by John

In the previous post I said that the Jacobi functions are like trig functions. That’s true if you look along the real axis. If you look at the rest of the complex plane you’ll see how they can be very different.

The sine function is periodic along the real axis, but it grows exponentially along the imaginary axis. I mentioned parenthetically last time that the Jacobi functions are not just periodic but doubly periodic. That means that not only are they periodic as you move along the real axis, they’re periodic when you move along any line in the complex plane [1].We’ll illustrate this with some plots.

It will make our code more compact if we first define a function to split a complex number into its real and imaginary parts.

    pair[z_] := {Re[z], Im[z]}

Here’s what it looks like when you plot the real and imaginary parts of the sine function along the line (10 + 0.5i)t.

    
    ParametricPlot[
        pair[ Sin[(0.5 I + 10)t] ], 
        {t, 0, 10}, 
        PlotRange -> All
    ]

plot of sine with complex argument

By contrast, here’s a plot of the sn function along the line 1.25 + it.

    ParametricPlot[
        pair[ JacobiSN[1.25 + I t, 0.5] ], 
        {t, 0, 10}
    ]

It’s a closed loop because sn is periodic in every direction. (By the way, the curve looks like an egg. More posts about egg-shaped curves starting here.)

When you plot sn along various lines you’ll always get closed curves, but you won’t always get such round curves. Here’s an example that doesn’t look like a closed loop because the curve turns around sharply at each end.

 
    ParametricPlot[
        pair[ JacobiCN[ (I + 0.5) t, 0.5] ], 
        {t, 0, 10}
    ]

To show that it really is periodic, we’ll add a vertical time dimension to visualize how the curve is traced out over time.

    triple[z_, t_] = {Re[z], Im[z], t}
    ParametricPlot3D[
        triple[JacobiSN[(I + 0.5) t, 0.5], 0.1 t], 
        {t, 0, 20}
    ]

Here’s another curve plotting sn along a different line.

    ParametricPlot[
        pair[ JacobiSN[(0.9 + I) t, 0.5] ], 
        {t, 0, 55},
        PlotRange -> All, 
        PlotPoints -> 100
    ]

As before, we can add a time dimension to imagine how the curve is traced out.

    ParametricPlot3D[
        triple[JacobiSN[(0.9 + I) t, 0.5], 0.1 t], 
        {t, 0, 150},
        PlotRange -> All,
        PlotPoints -> 200
]

Here’s a variation on the plot above that stretches the vertical axis so you can better see what’s going on.

   
    ParametricPlot3D[
        triple[JacobiSN[(0.9 + I) t, 0.5], 0.2 t], 
        {t, 0, 150},
        PlotRange -> All,
        PlotPoints -> 200
    ]

[1] To be more precise, elliptic functions are periodic in two linearly independent directions, and thus in any direction that’s an integer linear combination of those two directions. So they’re exactly periodic in a countable number of directions almost periodic in every other direction.

System of Jacobi elliptic functions

Posted on by John

Jacobi’s elliptic functions are sorta like trig functions. His functions sn and cn have names that reminiscent of sine and cosine for good reason. These functions come up in applications such as the nonlinear pendulum (i.e. when θ is too
large to assume θ is a good enough approximation to sin θ) and in conformal mapping.

I ran across an article [1] yesterday that shows how Jacobi’s three elliptic functions—sn, cn, and dn—could be defined by one dynamical system

\begin{eqnarray*} x' &=& yz \\ y' &=& -zx \\ z' &=& -k^2 xy \end{eqnarray*}

with initial conditions x(0) = 0, y(0) = 1, and z(0) = 1.

The parameter k is the modulus. (In Mathematica’s notation below, k² is the parameter. See this post on parameterization conventions.) As k decreases to 0, sn converges to sine, cn to cosine, and dn to 1. As k increases to 1, sn converges tanh, and cn and dn converge to sech. So you could think of k as a knob you turn to go from being more like circular functions (ordinary trig functions) to more like hyperbolic functions.

Since we have a dynamical system, let’s plot the solution, varying the modulus each time.The Jacobi functions are periodic (in fact they’re doubly periodic) and so the plots will be closed loops.

f[t_, m_] = {JacobiSN[t, m], JacobiCN[t, m], JacobiDN[t, m]}
ParametricPlot3D[f[t, 0.707], {t, 0, 10}, AspectRatio -> 1]

phase portrait k = 1/2

ParametricPlot3D[f[t, 0.99], {t, 0, 20}, AspectRatio -> 1]

phase portrait k = 1/2

ParametricPlot3D[f[t, 0.01], {t, 0, 20}, AspectRatio -> 1]

phase portrait k = 1/2

Note that this last plot is nearly flat because the modulus is small and so z is nearly constant. The small modulus also makes the phase portrait nearly circular because x is approximately sine and y is approximately cosine.

[1] Kenneth R. Meyer. Jacobi Elliptic Functions from a Dynamical Systems Point of View. The American Mathematical Monthly, Vol. 108, No. 8 (Oct., 2001), pp. 729-737

Commutative multiplication of triples

Posted on by John

The complex numbers make a field out of pairs of real numbers. The quaternions almost make a field out of four-tuples of numbers, though multiplication is not commutatative. Technically, quaternions form a division algebra.

Frobenius’s theorem says only real vector spaces that can be made into division algebras are the real numbers, complex numbers, and quaternions.

So can you multiply triples of real numbers? Sure. Cross product is one way, but there’s no “division” analog to cross product. For example, the cross product of any vector with itself is zero, so cross product has lots of zero divisors, non-zero elements that multiply to zero.

Frobenius tells us we can’t form triples of real numbers into a division algebra, but can we come closer to a division algebra than we get with cross products? It turns out we can! We can define a multiplication that is commutative, has an identity element, and has no zero divisors. But what’s missing? The multiplication doesn’t have the distributive property you’d have in a division algebra.

The multiplication operation is complicated to describe. For details see “A Commutative Multiplication of Number Triplets” by Frank R. Pfaff, The American Mathematical Monthly, Vol. 107, No. 2 (Feb., 2000), pp. 156-162.

More quaternion posts

Three things about dominoes

Posted on by John

Here are three things about dominoes, two easy and one more advanced.

Counting

First, how many pieces are there in a set of dominoes? A domino corresponds to an unordered pair of numbers from 0 to n. The most popular form has n = 6, but there are variations with other values of n. You can show that the number of dominoes is

{ n+1\choose 2} + n + 1

This is because there are n+1 possible numbers (since blanks are a possibility) and each one is either a double or not. The number of ways to choose two distinct numbers is the binomial coefficient and the number of doubles is n+1.

Another way to look at this is that we are selecting two things from a set of n+1 things with replacement and so the number of possibilities is

\left({ n+1\choose 2}\right) = {n+2 \choose 2}

where the symbol on the left is Stanley’s symbol for selection with replacement.

In any case, there are 28 dominoes when n = 6, 55 when n = 9, and 91 when n = 12.

Magic squares

There are a couple ways to make a magic square of sorts from a set of dominoes. To read more about this, see this post.

Domino magic square

Tiling

How many ways can you cover an m by n chess board with dominoes? The answer turns out to be

\sqrt{\prod_{k=1}^m \prod_{\ell=1}^n \left( 2\cos\left(\frac{\pi k}{m+1} \right) + 2i \cos\left(\frac{\pi \ell}{n+1} \right) \right)}

See this post for details.

Magical learning

Posted on by John

I asked two questions on twitter yesterday. The previous post summarized the results for a question about books that I asked from my personal Twitter account.

This post will summarize the results of a question I asked from @AnalysisFact.

Here are the results by category. Some are not strictly theorems but rather topics or conjectures.

Computer science

  • Curry-Howard correspondence
  • P=NP or not
  • Collatz Conjecture

Logic

  • Cohen’s forcing theorem
  • Godel’s Incompleteness theorem
  • Continuum hypothesis
  • Zorn’s lemma

Algebra and number theory

  • The ABC conjecture (theorem?)
  • Prime number theorem.
  • Riemann hypothesis
  • Fundamental theorem of finite abelian groups
  • Classification of finite simple groups
  • Fermat’s last theorem, the unpublished Fermat version

Topology and differential geometry

  • Thurston’s geometrization conjecture
  • Gauss Bonnet theorem
  • de Rham’s theorem
  • Grothendieck Riemann Roch theorem

Analysis

  • Banach-Tarski theorem.
  • Stokes theorem
  • Carleson-Hunt theorem
  • The epsilon/delta definition of continuity
  • Universal approximation theorem

Differential equations

  • Navier–Stokes existence and smoothness postulate
  • The relativistic version of the Shrodinger equation
  • Atiyah-Singer index theorem

Mathematical physics

  • E = mc²
  • Noether’s theorem
  • Liouville’s theorem

Miscellaneous

  • Existence of general equilibrium prices
  • Farkas’ lemma
  • The graph minor theorem
  • Central limit theorem

Mischievous genie

A couple people picked up the fact that in folk stories, being granted a wish doesn’t usually turn out well.

M. Shah: uh oh. Is this one of those malicious genies that twists language used to make the wish so that you are granted some horrific wish?

Jumpy the Hat: You now understand every single thing about irrational numbers but it’s all wasted because you’re cursed to become NJ Wildberger and you don’t think they exist

M Shah: or you want to thoroughly understand some theorem about Weierstrass’s monster. But little did anyone know that Weierstrass actually did have a pet monster. And it ends up biting your head off because it doesn’t like other things that are continuous.

Books you’d like to have read

Posted on by John

I asked on Twitter today for books that people would like to have read, but don’t want to put in the time and effort to read.

Here are the responses I got, organized by category.

Literature:

Math, Science, and Software:

History and economics

Religion and philosophy

Misc: