Author Archives: David Goldberg

A Surprising Pitfall of Human Judgement and How to Correct It

Introduction

Algorithms based on machine learning, deep learning, and AI are in the news these days. Evaluating the quality of these algorithms is usually done using human judgment. For example, if an algorithm claims to detect whether an image contains a pet, the claim can be checked by selecting a sample of images, using human judges to detect if there is a pet, and then comparing this to the results to the algorithm. This post discusses a pitfall in using human judgment that has been mostly overlooked until now.

In real life, human judges are imperfect. This is especially true if the judges are crowdsourced. This is not a new observation. Many proposals to process raw judgment scores and improve their accuracy have been made. They almost always involve having multiple judges score each item and combining the scores in some fashion. The simplest (and probably most common) method of combination is majority vote: for example, if the judges are rating yes/no (for example, is there a pet), you could report the rating given by the majority of the judges.

But even after such processing, some errors will remain. Judge errors are often correlated, and so multiple judgments can correct fewer errors than you might expect. For example, most of the judges might be unclear on the meaning of “pet”, incorrectly assume that a chicken cannot be a pet, and wrongly label a photo of a suburban home showing a child playing with chickens in the backyard. Nonetheless, any judgment errors remaining after processing are usually ignored, and the processed judgments are treated as if they were perfect.

Ignoring judge errors is a pitfall. Here is a simulation illustrating this. I’ll use the pet example again. Suppose there are 1000 images sent to the judges and that 70% of the images contain a pet. Suppose that when there is no pet, the judges (or the final processed judgment) correctly detect this 95% of the time. This is actually higher than typical for realistic industrial applications. And suppose that some of the pet images are subtle, and so when there is a pet, judges are correct only 90% of the time. I now present a simulation to show what happens.

Here’s how one round of the simulation works. I assume that there are millions of possible images and that 70% of them contain a pet. I draw a random sample of 1000. I assume that when the image has a pet, the judgment process has a 90% chance reporting “pet”, and when there is no pet, the judgment process reports “no pet” 95% of the time. I get 1000 judgments (one for each image), and I record the fraction of those judgments that were “pet”.

That’s one round of the simulation. I do the simulation many times and plot the results as a histogram. I actually did 100,000 simulations, so the histogram has 100,000 values. The results are below in red. Since this is a simulation, I know the true fraction of images with pets: it’s 70%. The estimated fraction from the judges in each simulation is almost always lower than the true fraction. Averaged over all simulations, the estimated fraction is 64%, noticeably lower than the true value of 70%.

This illustrates the pitfall: by ignoring judge error, you get the wrong answer. You might wonder if this has any practical implications. How often do you need a precise estimate for the fraction of pets in a collection of images? But what if you’re using the judgments to determine the accuracy of an algorithm that detects pets? And suppose the algorithm has an accuracy rate of 70%, but the judges say it is 64%. In the machine learning/AI community, the difference between an algorithm that is 70% accurate vs 64% is a big deal.

But maybe things aren’t as bad as they seem. When statistically savvy experimenters report the results of human judgment, they return error bars. The error bars (I give details below) in this case are

    \[       0.641 \pm 1.96 \sqrt{\frac{p (1-p)}{n}} \approx 0.641 \pm 0.030 \qquad (p = 0.64) \]

So even error bars don’t help: the actual accuracy rate of 0.7 is not included inside the error bars.

The purpose of this post is to show that you can compensate for judge error. In the image above, the blue bars are the simulation of the compensating algorithm I will present. The blue bars do a much better job of estimating the fraction of pets than the naive algorithm. This post is just a summary, but full details are in Drawing Sound Conclusions from Noisy Judgments from the WWW17 conference.

The histogram shows that the traditional naive algorithm (red) has a strong bias. But it also seems to have a smaller variance, so you might wonder if it has a smaller mean square error (MSE) than the blue algorithm. It does not. The naive algorithm has MSE 0.0037, the improved algorithm 0.0007. The smaller variance does not compensate for the large bias.

Finally, I can explain why judge error is so important. For a typical problem requiring ML/AI, many different algorithms are tried. Then human judgment can be used to detect if one is better than the other. Current practice is to use error bars as above, which do not take into account errors in the human judgment process. But this can lead the algorithm developer astray and suggest that a new algorithm is better (or worse) when in fact the difference is just noise.

The setup

I’m going to assume there are both an algorithm that takes an input and outputs a label (not necessarily a binary label) and also a judge that decides if the output is correct. So the judge is performing a binary task: determining if the algorithm is correct or not. From these judgments, you can compute the fraction of times (an estimate of the probability p) that the algorithm is correct. I will show that if you can estimate the error in the judgment process, then you can compensate for it and get a better estimate of the accuracy of the algorithm. This applies if you use raw judge scores or if you use a judgment process (for example, majority vote) to improve judge accuracy. In the latter case, you need to estimate the accuracy of the judgment process.

A simple example of this setup is an information retrieval algorithm. The algorithm is given a query and returns a document. A judge decides if the document is relevant or not. A subset of those judgments is reevaluated by gold judge experts, giving an estimate of the judges’ accuracy. Of course, if you are rich enough to be able to afford gold judges to perform all your labeling, then you don’t need to use the method presented here.

A slightly more subtle example is the pet detection algorithm mentioned above. Here it is likely that there would be a labeled set of images (a test set) used to evaluate the algorithm. You want to know how often the algorithm agrees with the labels, and you need to correct for errors in the judgment about agreement. To estimate the error rate, pick a subset of images and have them rejudged by experts (gold judges). The judges were detecting if an image had a pet or not. However, what I am really interested in is the error rate in judging whether the algorithm gave the correct answer or not. But that is easily computed from the gold judgments of the images.

The first formula

In the introduction, I mentioned that there are formulas that can correct for judge error. To explain the formula, recall that there is a task that requires labeling items into two classes, which I’ll call positive and negative. In the motivating example, positive means the algorithm gives the correct output for the item, negative that it is incorrect. I have a set of items, and judges perform the task on each item, getting an estimate of how many items are in the positive class. I’d like to use information on the accuracy of the judges to adjust this estimate. The symbols used in the formula are:

Rendered by QuickLaTeX.com

The first formula is

    \[ p = \frac{p_J + q_- - 1}{q_+ + q_- -1} \]

This formula is not difficult to derive. See the aforementioned WWW paper for details. Here are some checks that the formula is plausible. If the judges are prefect then q_+ = q_- = 1, and the formula reduces to p = p_J. In other words, the judges’ opinion of p is correct. Next, suppose the judges are useless and guess randomly. Then q_+ = q_- = 1/2, and the formula makes no sense because the denominator is infinity. So that’s also consistent.

Notice the formula is asymmetric: the numerator has q_- but not q_+. To see why this makes sense, first consider the case when the judges are perfect on negative items so that q_- = 1. The judges’ only error is to take correct answers and claim they are negative. So an estimate of p by the judges is always too pessimistic. On the other hand, if q_+ = 1, then the judges are optimistic, because they sometimes judge incorrect items as correct.

I will now show that the formula achieves these requirements. In particular, if q_- = 1 then I expect p_J < p and if q_+ = 1 then p_J > p. To verify this, note that if q_- = 1 the formula becomes p = p_J/q_+ > p_J. And if q_+ = 1 then

    \begin{eqnarray*}   p  &=& \frac{p_J + q_- - 1}{q_-} \\ &=& \frac{p_J - 1}{q_-} + 1 \\ &=& \frac{p_J - 1}{q_-} + (1-p_J) + p_J \\   &= & (p_J - 1)\left(\frac{1}{q_-} - 1\right) + p_J \\   & < & p_J \end{eqnarray*}

the last inequality because p_J - 1 < 0 and 1/q_- -1 > 0.

Up until now the formula is theoretical, because the precise values of p_J, q_+ and q_- are not known. I introduce some symbols for the estimates.

Rendered by QuickLaTeX.com

The practical formula is

    \[ \widehat{p} = \frac{\widehat{p}_J + \widehat{q}_\text{--} - 1}{\widehat{q}_+ + \widehat{q}_\text{--} -1} \]

The second formula

In the introduction, I motivated the concern with judgment error using the problem of determining the accuracy of an ML algorithm and, in particular, comparing two algorithms to determine which is better. If you had perfect judges and an extremely large set of labeled data, you could measure the accuracy of each algorithm on the large labeled set, and the one with the highest accuracy would clearly be best. But the labeled set is often limited in size. That leads to some uncertainty: if you had picked a different labeled set you might get a difference answer. That is the purpose of error bars: they quantify the uncertainty. Traditionally, the only uncertainty taken into account is due to the finite sample size. In this case, the traditional method gives 95% error bars of \widehat{p}_J  \pm 2 \sqrt{v_{\widehat{p}_J}} where

    \begin{eqnarray*}       \widehat{p}_J  &=&  \frac{k}{n} \\       v_{\widehat{p}_J} &= &  \frac{\widehat{p}_J(1-\widehat{p}_J)}{n} \end{eqnarray*}

The judge gave a positive label k times out of n, \widehat{p}_J is the estimated mean and v_{\widehat{p}_J} the estimate of the variance of \widehat{p}_J. I showed via simulation that if there are judgment errors, these intervals are too small. The corrected formula is

    \[ v_{\widehat{p}} =  \frac{v_{\widehat{p}_J}}{(\widehat{q}_+ + \widehat{q}_\text{--} - 1)^2} + v_{\widehat{q}_+}\frac{(\widehat{p}_J - 1 + \widehat{q}_\text{--})^2}{(\widehat{q}_+ + \widehat{q}_\text{--} - 1)^4} + v_{\widehat{q}_\text{--}}\frac{(\widehat{p}_J - \widehat{q}_+)^2}{(\widehat{q}_+ + \widehat{q}_\text{--} - 1)^4} \]

where

Rendered by QuickLaTeX.com

The formula shows that when taking judge error into account, the variance increases, that is, v_{\widehat{p}} >  v_{\widehat{p}_J}. The first term of the equation for v_{\widehat{p}} is already larger than v_{\widehat{p}_J}, since is it v_{\widehat{p}_J} divided by a number less than one. The next two terms add additional error, due to the uncertainty in estimating the judge errors \widehat{q}_+ and \widehat{q}_-.

Extensions

The theme of this post is correcting for judge errors, but I have only discussed the case when the judge gives each item a binary rating, as a way to estimate what fraction of items are in each of the two classes. For example, the judge reports if an algorithm has given the correct answer, and you want to know how often the algorithm is correct. Or the judge examines a query and a document, and you want to know how often the document is relevant to the query.

But the methods presented so far extend to other situations. The WWW paper referred to earlier gives a number of examples in the domain of document retrieval. It explains how to correct for judge error in the case when a judge gives documents a relevance rating rather than just a binary relevant or not. And it shows how to extend these ideas beyond the metric “fraction in each class” to the metric DCG, which is a common metric for document retrieval.

Assumptions

Analyses of the type presented here always have assumptions. The assumption of this work is that there is a task (for example, “is the algorithm correct on this item?”) with a correct answer and that there are gold judges who are expert enough and have enough time to reliably obtain that correct answer. Industrial uses of human judgment often use detailed guidelines explaining how the judgment should be done, in which case these assumptions are reasonable.

But what about the general case? What if different audiences have different ideas about the task? For example, there may differences from country to country about what constitutes a pet. The analysis presented here is still relevant. You only need to compute the error rate of the judges relative to the appropriate audience.

I treat the judgment process as a black box, where only the overall accuracy of the judgments is known. This is sometimes very realistic, for example, when the judgment process is outsourced. But sometimes details are known about the judgment process would lead you to conclude that the judgments of some items are more reliable than others. For example, you might know which judges judged which items, and so have reliable information on the relative accuracy of the judges. The approach I use here can be extended to apply in these cases.

The simulation

I close this post with the R code that was used to generate the simulation given earlier.

# sim() returns a (n.iter x 4) array, where each row contains:
#   the naive estimate for p,
#   the corrected estimate,
#   whether the true value of p is in a 95% confidence interval (0/1)
#        for the naive standard error
#   the same value for the corrected standard error

sim = function(
  q.pos,  # probability a judge is correct on positive items
  q.neg,  # probability a judge is correct on negative items
  p,      # fraction of positive items
  n,      # number of items judged
  n.sim,  # number of simulations
  n.gold.neg = 200, # number of items the gold judge deems negative
  n.gold.pos = 200  # number of items the gold judge deems positive
  )
{
   # number of positive items in sample
   n.pos = rbinom(n.sim, n, p)

   # estimate of judge accuracy
   q.pos.hat = rbinom(n.sim, n.gold.pos, q.pos)/n.gold.pos
   q.neg.hat = rbinom(n.sim, n.gold.neg, q.neg)/n.gold.neg

   # what the judges say (.jdg)
   n.pos.jdg = rbinom(n.sim, n.pos, q.pos) +
               rbinom(1, n - n.pos, 1 - q.neg)

   # estimate of fraction of positive items
   p.jdg.hat = n.pos.jdg/n    # naive formula
   # corrected formula
   p.hat = (p.jdg.hat - 1 + q.neg.hat)/
                      (q.neg.hat + q.pos.hat - 1)

   # is p.jdg.hat within 1.96*sigma of p?
   s.hat =  sqrt(p.jdg.hat*(1 - p.jdg.hat)/n)
   b.jdg = abs(p.jdg.hat - p) < 1.96*s.hat

   # is p.hat within 1.96*sigma.hat of p ?
   v.b = q.neg.hat*(1 - q.neg.hat)/n.gold.neg   # variance q.neg
   v.g = q.pos.hat*(1 - q.pos.hat)/n.gold.pos
   denom = (q.neg.hat + q.pos.hat - 1)^2
   v.cor = s.hat^2/denom +
           v.g*(p.jdg.hat - 1 + q.neg.hat)^2/denom^2 +
           v.b*(p.jdg.hat - q.pos)^2/denom^2
   s.cor.hat = sqrt(v.cor)
   # is negative.jdg.rate.cor within 1.96*sigma of p?
   b.cor = abs(p.hat - p) < 1.96*s.cor.hat

   rbind(p.jdg.hat, p.hat, b.jdg, b.cor)
}

set.seed(13)
r = sim(n.sim = 100000, q.pos = 0.90,  q.neg = 0.95, p = 0.7, n=1000)

# plot v1 and v2 as two separate histograms, but on the same ggplot
hist2 = function(v1, v2, name1, name2, labelsz=12)
{
  df1 = data.frame(x = v1, y = rep(name1, length(v1)))
  df2 = data.frame(x = v2, y = rep(name2, length(v2)))
  df = rbind(df1, df2)

  freq = aes(y = ..count..)
  print(ggplot(df, aes(x=x, fill=y)) + geom_histogram(freq, position='dodge') +
      theme(axis.text.x = element_text(size=labelsz),
      axis.text.y = element_text(size=labelsz),
      axis.title.x = element_text(size=labelsz),
      axis.title.y = element_text(size=labelsz),
      legend.text = element_text(size=labelsz))
  )
}

hist2(r[1,], r[2,], "naive", "corrected", labelsz=16)

Powered by QuickLaTeX.

Congruent Numbers Part III

Before demonstrating the claims made in Part I and Part II on this topic, let me mention two simple facts about integer solutions to A^2 + B^2 = C^2. First, if some number d divides both A and B, it also clearly divides C. So A and B have a common factor if and only if A, B, and C do. Or saying it another way, A and B are relatively prime if and only if A, B, and C are. From now on I always assume that this is true for A, B, and C.

The second fact is that A and B have opposite parity, that is, one is even and the other odd. It’s clear that A and B can’t both be even, since then they would have a common factor of 2. To see that A and B can’t both be odd, note that the square of an odd number is (2d+1)^2 = 4(d^2 + d) + 1 so the square of an odd number is congruent to 1 modulo 4. This means that if A and B are both odd, the left side of A^2 + B^2 = C^2 is congruent to 2 modulo 4. But then the right-hand side is even, so is of the form (2d)^2 = 4d^2 and is congruent to 0 modulo 4, contradiction.

With these two facts out of the way, let me show that a Pythagorean triple A^2 + B^2 = C^2 is always of the form

(1)   \begin{eqnarray*} A &=& 2PQ  \\ B &=& P^2 - Q^2 \qquad (\mbox{with } P > Q) \nonumber \\ C &=& P^2 + Q^2 \nonumber \end{eqnarray*}

It is easy to check that if A, B and C can be written this way in terms of P and Q then A^2 + B^2 = C^2. But where does the formula come from, and why are there always such P and Q?

A Pythagorean triple can be thought of as a point (x,y) on a unit circle:

(2)   \begin{equation*}\arraycolsep=1.4pt \begin{array}{ccccc} A^2 & + & B^2 & = & C^2 \\ \displaystyle \left(\frac{A}{C}\right)^2 & + & \displaystyle \left( \frac{B}{C}\right)^2 &=& 1 \\ \rule{0pt}{15pt}x^2 & + & y^2 & = & 1 \end{array} \end{equation*}

Each point (x,y) corresponds to a single point z on the x-axis, as in the left half of the figure below. The slanted line connects (0, 1) to a point z on the x-axis.

pythagThe key fact is that each pair (x,y) corresponds to a single number z. And z is rational if and only if (x,y) is rational. This can be seen from explicit formulas linking (x,y) and z. To get those formulas consult the right half of the figure where the triangle with sides E, F is proportional to the triangle with sides G, H. So

    \begin{eqnarray*} \frac{F}{E} & = & \frac{H}{G} \\ \frac{x}{1 - y} & = & z \\ z^2(1-y)^2 & = & x^2 = 1 - y^2 \\ z^2(1-y)(1-y) & = & (1-y)(1+y) \\ z^2(1-y) & = & 1+y \\ z^2 - 1 & = & (z^2 + 1)y \\ y & = & \frac{z^2 - 1}{z^2 + 1} \\ x & = & \frac{2z}{z^2 + 1} \end{eqnarray*}

The second equation shows that if x and y are rational then so is z. And the last two equations show the converse. But they show more. Writing z = P/Q in reduced form (i.e. P and Q relatively prime) and combining with (2) shows

    \begin{eqnarray*} x = \frac{A}{C}& = & \frac{2z}{z^2+1} \; = \; \frac{2PQ}{P^2 + Q^2}\\ y = \frac{B}{C} & = & \frac{z^2-1}{z^2+1} \;=\; \frac{P^2 - Q^2}{P^2 + Q^2} \end{eqnarray*}

Equating numerators suggests that A = 2PQ and B = P^2 - Q^2. But there is a subtlety: this is guaranteed only if A and B are relatively prime. For example 9^2 + 12^2 = 15^2, but there are no P and Q with 12 = 2PQ and 9 = P^2 - Q^2. The small print below gives two ways to turn the suggestion into a proof.

Both {\scriptstyle A/C} and {\scriptstyle B/C} are in reduced form since {\scriptstyle A} and {\scriptstyle B} are relatively prime. Therefore, the equation above shows only that there is an integer {\scriptstyle k} with
{\scriptstyle \mbox{ } kA = 2PQ \qquad kC = P^2 + Q^2 \qquad kB = P^2 - Q^2}
So I need to show that {\scriptstyle k=1}. First note that by adding and subtracting the last two equations, {\scriptstyle k|2P^2} and {\scriptstyle k|2Q^2}. Since {\scriptstyle P/Q} is in lowest form, at least one is odd so {\scriptstyle k} cannot be divisible by 4. Also, {\scriptstyle k} cannot be divisible by an odd prime {\scriptstyle p}, since that would then be a common factor of {\scriptstyle P} and {\scriptstyle Q}. So {\scriptstyle k} is either 1 or 2. Suppose {\scriptstyle k=2}. Since {\scriptstyle A/C}, and {\scriptstyle B/C} are reduced, they aren’t all even; and since {\scriptstyle A^2 + B^2 = C^2} one of {\scriptstyle A} and {\scriptstyle B} is odd. The geometric construction works when you switch {\scriptstyle x} and {\scriptstyle y}, so I can assume that {\scriptstyle B} is odd. Then {\scriptstyle kB = 2B \equiv 2 \pmod 4}. If {\scriptstyle P} and {\scriptstyle Q} have the same parity, then {\scriptstyle P^2 - Q^2 \equiv 0 \pmod 4}. So they must have opposite parities. But then {\scriptstyle P^2 - Q^2} is odd and can’t equal {\scriptstyle kB = 2B}, contradiction. Therefore {\scriptstyle k=1}. Forcing {\scriptstyle B} to be odd is crucial. If {\scriptstyle B} is even, {\scriptstyle k > 1} is possible. For example {\scriptstyle B=4, A=3, C=5} has a solution {\scriptstyle P=3}, {\scriptstyle Q=1}, {\scriptstyle k=2}.There’s also a fancy proof that uses unique factorization in the ring {\scriptstyle \mathbb{Z}[i]}. Write {\scriptstyle A^2 + B^2 = (A+iB)(A-iB) = C^2}. The two numbers {\scriptstyle A \pm iB} are relatively prime (see below) so each prime factor of {\scriptstyle C^2} divides only one of them. Therefore, each is a square and {\scriptstyle A+iB = \epsilon(P+iQ)^2} where {\scriptstyle \epsilon} is {\scriptstyle \pm 1} or {\scriptstyle \pm i}. So {\scriptstyle A+iB = (P^2 - Q^2) + i2PQ}, possibly switching {\scriptstyle A} and {\scriptstyle B}.

To see that the relative primality of {\scriptstyle A} and {\scriptstyle B} implies the relative primality {\scriptstyle A \pm iB}, suppose that a complex integer {\scriptstyle Z} divides both of {\scriptstyle A \pm iB}. If {\scriptstyle Z} is a real integer, then it divides both {\scriptstyle A} and {\scriptstyle B}, contradicting their relative primality. Similarly if {\scriptstyle Z} is purely imaginary. That means I can assume that {\scriptstyle Z \neq \overline{Z}}. By conjugating, it follows that {\scriptstyle \overline{Z} | A \pm iB} and so both {\scriptstyle Z} and {\scriptstyle \overline{Z}} divide {\scriptstyle A+iB}. Since these are distinct, the real integer {\scriptstyle |Z|^2} divides {\scriptstyle A+iB} which is again a contradiction. The final detail is that although {\scriptstyle Z \neq \overline{Z}}, they could be associates, that is {\scriptstyle Z = \pm iZ}. But that would imply {\scriptstyle Z = K(1\pm i)} so {\scriptstyle 1 \pm i | A + iB} which after taking norms becomes {\scriptstyle 2 | A^2 + B^2}, and that contradicts the statement from the beginning of this post that {\scriptstyle A} and {\scriptstyle B} are of opposite parity.

Formula (1) gives an easy way to show why there isn’t a triangle with integer sides and area 5. If \frac{1}{2}AB = N then that formula shows that there is a pair P, Q with (P,Q) = 1 and

    \[ PQ(P - Q)(P+Q) = N \]

When N=5 this has no integer solution because three of the factors must be 1, the other 5. Since P+Q is the largest of the four factors, it would have to be 5 and P = Q = P - Q = 1, which is clearly impossible.

Since the numbers A, B, C, and D are used to compute the sides \alpha = A/D, \beta = B/D and \gamma = C/D, you can remove any common factors if necessary since that won’t change the side lengths \alpha, \beta, \gamma. So I will always assume that \gcd(A,B,C,D) = 1, or using a common shorthand (A,B,C,D) =1.

Proposition: If A,B,C,D represents a square-free congruent triangle and (A,B,C,D) = 1, then (A,B,C) = 1.

Proof: By contradiction. Suppose (A,B,C) > 1. Then some prime p divides (A,B,C). First suppose p = 2 so 2 | (A,B,C) but 2 \nmid D. Then A'= A/2, B'= B/2, and C'= C/2 are integers so A'^2 + B'^2 = C'^2. It follows that one of A' or B' is even. This means that one of A, B is divisible by 4, the other by 2, so 8 | AB. Since \frac{1}{2}(A/D)(B/D) = N

    \[ \frac{1}{2}AB = N D^2 \]

It follows that 4|ND^2, but 2 \nmid D and N is square free. This is a contradiction, so 2 \nmid (A,B,C). Similarly, if p is an odd prime, and p divides A, B, and C but not D, then p^2|N, contradiction. So (A,B,C) = 1. \; {\rule{.6ex}{1.8ex}}

I use this to give a shortcut in the exhaustive search over P and Q. You only need to consider a subset. In the lemma below, the parity of N is N \pmod 2, i.e. odd or even.

Lemma: For a square-free congruent triangle, if (A,B,C,D) = 1 then (P,Q) = 1 and P, Q are of opposite parity. And such pair of (P,Q) generates a triangle with (A,B,C,D) = 1.

Proof:
First assume (A,B,C,D) = 1. If P and Q have the same parity, then from equation (1) all of A, B and C are even, contradicting the proposition. If P and Q have a common factor, so do A, B and C, so that is not possible either. For the other direction, note that since P and Q have different parities, then A is odd and B is even so 2 \nmid (A,B, C). Thus you only need to consider an odd prime p. If p|(A,B,C) then p|B+C so p|2P^2 so p|P and similarly p|Q. \; {\rule{.6ex}{1.8ex}}

It follows that in exhaustive search, you only need to consider P, Q that are relatively prime and of opposite parities. Note: this is the glitch in the web table I mentioned earlier. For N=559, the web table gives P=2608225, Q=4489, which are both odd. If you use them to generate (A,B,C,D), remove the common factor of 2, and then recompute P, Q you get P' = 1306357, Q'= 1301868 with P' < P.

Next, I’ll verify the important speedup, which is that P and Q are almost squares.

Proposition: If P, Q are relatively prime and generate a square-free congruent number, then P = sP_0^2 and Q = tQ_0^2 where st|N (in particular, s|N and t|N).

Proof: Combine equation (1) and \frac{1}{2}\alpha \beta = \frac{1}{2}(A/D)(B/D) = N to get

    \[ D^2N = \frac{1}{2}AB = \left(P^2 - Q^2\right) PQ \qquad (P,Q) = 1 \]

If a prime p has p | P then p|N or p|D. If the latter, p^2 | (P^2 - Q^2)PQ but since (P,Q) = 1), p|Q is impossible, and so p|(P^2 - Q^2) is impossible so p^2 | P. Therefore every factor of P is either a square or a factor of N. It follows that P = sP_0^2 where each factor of s divides N. If any factor of s is a square then incorporate it into P_0 after which s|N. Similarly Q = tQ_0^2. Since (P,Q) = 1, (s,t) = 1 so st|N. \; {\rule{.6ex}{1.8ex}}

We observed earlier that in our tables, the denominator of \alpha times the denominator of \beta equals the denominator of \gamma. Here is the proof that it is true in general. Repeating the equations:

    \[\alpha = \frac{a}{d} \qquad \beta = \frac{b}{d} \qquad \gamma = \frac{c}{d}\]

    \begin{eqnarray*} \left(\frac{a}{d}\right) ^2 + \left(\frac{b}{e}\right) ^2 & = & \left(\frac{c}{f}\right) ^2 \\ \left(\frac{A}{D}\right) ^2 + \left(\frac{B}{D}\right) ^2 & = & \left(\frac{C}{D}\right) ^2 \end{eqnarray*}

Even though (A,B,C,D) = 1, A and D can have a common factor in which case a \neq A and b \neq B.

Lemma: With the usual assumption that (A,B,C,D) = 1, then de=f.

Proof: First check that (C,D) = 1 so that f=D. If not, then there is a p > 1 with p|D and p|C. From p|D and

(3)   \begin{equation*}  AB = 2nD^2 \end{equation*}

it follows that p|A (or perhaps B). But p|C and A^2 + B^2 = C^2 implies p|(A,B,C), contradiction. Next from (3) every prime factor of D must divide either A or B. Start with A/D and B/D. Then consider the prime factors of D one-by-one. For each factor p, remove it from either the numerator and denominator of A/D or from B/D. After the removal process A/D becomes A'/D' and B/D becomes B'/D'' and since a/d and b/d are completely reduced, d|D', e|D'' and so de | D'D''. Since each factor of D was removed, D'D'' = D so de | D'D'' = D and thus de \leq D. Finally, write

    \begin{eqnarray*} \frac{A^2}{D^2} + \frac{B^2}{D^2} & = & \frac{C^2}{D^2} \\ \frac{a^2}{d^2} + \frac{b^2}{e^2} & = & \frac{C^2}{D^2} \\ \frac{a^2e^2 + b^2d^2}{d^2e^2} & = & \frac{C^2}{D^2} \end{eqnarray*}

The last equation shows that de \geq D. If not, then it writes C^2/D^2 in a more reduced form, contradicting the first part of the proof. I previously showed de \leq D so it follows that de = D. And the first part of the proof showed that f=D. \; {\rule{.6ex}{1.8ex}}

Powered by QuickLaTeX

Congruent Numbers Part II

Using Elliptic Curves to Compute the Triangles

The method of my first post is too slow to find the side lengths for a triangle of area N=157, which has many digits:

    \[ \left(\frac{6803298487826435051217540}{411340519227716149383203}\right)^2 + \left(\frac{411340519227716149383203}{21666555693714761309610}\right)^2 \]

    \[ = \left(\frac{224403517704336969924557513090674863160948472041}{8912332268928859588025535178967163570016480830} \right)^2 \]

    \[ \rule{0pt}{30pt} \frac{1}{2} \times \frac{6803298487826435051217540}{411340519227716149383203} \times \frac{411340519227716149383203}{21666555693714761309610} = 157 \]

In the 1984 book by Koblitz,  Introduction to Elliptic Curves and Modular Forms, computation of the side lengths for N=157 is credited to the mathematician Don Zagier. Now, however, it can be computed quickly by anyone with access to the SageMath system. The Python code given below computes the values for N=157 in less than one minute on my Mac laptop.

Put the code in the next section into a file called (say) congruent.py, fire up SageMath, and then type load(‘congruent.py’) followed by print_range(157, 157, 13). This produces the answer in about 15 seconds.

This post has three parts: I derive equations that produce triangle side lengths for congruent numbers; I give Python code that implements the equations; and I present two tables of congruent numbers. The first table is for N \leq 1000, and is a variant of the web table. The second is an incomplete table for 1000 < N \leq 2000 constructed using the Python code.

The equations

Exhaustive search is too slow to find the sides of the triangle with area N=157; finding them requires a new idea. That idea is to reduce the search to a problem in elliptic curves (the same idea used to prove Fermat’s Last Theorem!).

An elliptic curve is the next level of complexity after a quadratic curve. A quadratic curve is y^2 = ax^2 + bx + c; an elliptic curve is y^2 = ax^3 + bx^2 + cx + d. For the congruent number problem, Koblitz’s book Introduction to Elliptic Curves and Modular Forms shows the connection between a congruent N and the elliptic curve y^2 = x^3 - N^2x. I summarize it here.

The connection involves adding points. For a conic section like a circle x^2 + y^2 = 1 each point (x,y) can be represented by (\cos \theta, \sin \theta), and two points (x,y), (x', y') with angles \theta, \theta' can be added to get a third point (x'', y'') with angle \theta + \theta'. In a formula

    \[ x'' = \cos(\theta + \theta') = \cos \theta \cos \theta' - \sin \theta \sin \theta' = xx' - yy' \]

with a similar formula for y''. So the formula for (x,y) \oplus (x', y') is a rational function of x,y,x', y', where \oplus is our special addition, not vector addition. In the same way, two points on an elliptic curve can be added, and there is a formula for the sum. If y^2 = f(x) = ax^3 = bx^2 + cx + d and (x', y') = (x,y) \oplus (x,y) then the formula for x' (I don’t need y') is

    \[ x' = -2x - \frac{b}{a} + \frac{1}{a}\left( \frac{f'(x)}{2y} \right)^2 \]

If (x,y) is a point of

    \[ y^2 = x^3 - N^2x \]

this simplifies to

    \[ x' = -2x + \left( \frac{3x^2 - N^2}{2y} \right)^2 \]

In that equation x', x and y are rational numbers. I need a formula in terms of their numerators and denominators. So write

(1)   \begin{equation*}  x = \frac{s}{t} \qquad y = \frac{u}{v} \end{equation*}

Then

    \begin{eqnarray*} x' & = & -2\frac{s}{t} + \left( \frac{3(\frac{s}{t})^2 - N^2}{\frac{2u}{v}} \right)^2 \\ & = & -\frac{2s}{t} + \left(\frac{3s^2v - t^2vn^2}{2ut^2}\right)^2 \\ & = & -\frac{2s}{t} + \frac{v^2}{4u^2t^4}\left(3s^2 - t^2n^2 \right)^2 \\ & = & -\frac{8su^2t^3}{4u^2t^4} + \frac{v^2\left(3s^2 - t^2n^2 \right)^2}{4u^2t^4} \\ & = & \frac{-8su^2t^3 + v^2\left(3s^2 - t^2n^2 \right)^2}{(2ut^2)^2} \\ & = & \frac{s'}{t'} = \frac{s'}{\tau^2} \end{eqnarray*}

Next, use Koblitz page 47, which says that if (x',y') is the \oplus sum of a point on y^2 = x^3 - N^2x with itself, then you get rational sides with area N for sides \alpha, \beta with

    \begin{eqnarray*} \alpha & = & \sqrt{x'+N} - \sqrt{x'-N} \\ \beta & = & \sqrt{x'+N} + \sqrt{x'-N} \\ \end{eqnarray*}

so

    \begin{eqnarray*} \alpha & = & \sqrt{x'+N} - \sqrt{x'-N} = \frac{\sqrt{s' + Nt'} - \sqrt{s' - Nt'}}{\tau} \\ \beta & = & \sqrt{x'+N} + \sqrt{x'-N} = \frac{\sqrt{s' + Nt'} + \sqrt{s' - Nt'}}{\tau} \end{eqnarray*}

Or since \alpha = a/d, \beta = b/e

    \begin{eqnarray*} a &=& \sqrt{s' + Nt'} - \sqrt{s' - Nt'} \\ d &=& \tau \\ b &=& \sqrt{s' + Nt'} + \sqrt{s' - Nt'}\\ e &=& d \end{eqnarray*}

This gives an algorithm that can find the sides’ lengths for area N, and is fast enough to work for N=157. Use SageMath to find a point on y^2 = x^3 - Nx. Next use equation (1) to define s, t, u, v and the equation after that to get s' and t'. And use the equations directly above to get the side lengths \alpha = a/d and \beta = b/e.

Python code for SageMath

Here is the code that implements the algorithm of the previous section.

# congruent in python for use in SageMath

import re

# print sides of congruent number from lo to hi, inclusive
def print_range(lo, hi, lim=12):
    for i in range(lo, hi+1):
        if (squarefree(i) == 1):
            if  ((i%2 == 1) and odd(i)) or ((i%2 == 0) and even(i)):
                print_congruent(i, lim)

# return 1 if n squarefree
def squarefree(n):
    if n % 4 == 0:
        return 0
    rt = floor(sqrt(n))
    for i in range(3, rt+1, 2):
       if n % (i*i) == 0:
           return 0
    return 1

# print sides of triangle with area N.  'lim' controls how much searching is done
def print_congruent(N, lim=12):
   e = EllipticCurve([-N*N, 0])
   try:
       g = e.gens(descent_second_limit = lim)
   except (RuntimeError) as msg:
       #  msg might be of the form "generators found=[[323144640, -6423052104, 274625]])."
       match = re.search(r"\[([0-9-]*),(.*),([0-9- ]*)", str(msg))
       if match is not None:
          preparser(False)
          a = int(match.group(1))
          b = int(match.group(2))
          c = int(match.group(3))
          preparser(True)
          print_points(a, c, b, c, N)
       else:
          print N, "Cannot find Solution"
   else:
      for i in range(0, len(g)):
          print_points(g[i][0].numerator(), g[i][0].denominator(), g[i][1].numerator(),
                g[i][1].denominator(), N)

# Get the side lengths alpha = a/d, beta = b/e, compute
# the corresponding values of P,Q, write them as a square
# times a factor of N,  and print them
def print_points(s,t,u,v, N):  # pts x=s/t, y=u/v on elliptic curve
   s1, t1, u1, v1 = double(s, t, u, v, N)
   a, d, b, e = point_to_sides(s1, t1, N)        
   print N, "   alpha=", a, "/", d
   print "      beta=", b, "/", e

   #  compute A,B,C so that A^2 + B^2 = C^2
   A = a*e
   B = b*d
   g = gcd(A,B)
   A = A/g
   B = B/g
   C = sqrt(A*A + B*B)

   # compute P,Q so that A = 2PQ, B = P^2 - Q^2
   if B % 2 == 1:
      P = sqrt((C+B)/2)
      Q = sqrt((C-B)/2)
      print "     P=", P, " Q=", Q
   else:
      P = sqrt((C+A)/2)
      Q = sqrt((C-A)/2)
      print "     P=", P, " Q=",  Q

   # factor P = i0*P0^2,  Q = j0*Q0^2
   for i in range(1, N+1):
       if ( P%i == 0 and floor(sqrt(P/i))**2 == P/i):
            P0 = sqrt(P/i)
            i0 = i
            break
   for j in range(1, N+1):
       if (Q%j == 0 and  floor(sqrt(Q/j))**2 == Q/j):
            Q0 = sqrt(Q/j)
            j0 = j
            break
   print "    P= ", i0, "*", P0, "^2, Q=", j0, "*", Q0, "^2"

# x=s/t, y=u/v is a point on y^2 = x^3 - N^2x.  Returns (x,y) + (x,y)
def double(s,t,u,v, N): 
   num = -8*s*t**3*u*u + v*v*(3*s*s - t*t*N*N)**2
   denom = 2*u*t*t
   s1 = num
   t1 = denom*denom
   u1 = -2*u*u*t1*t**3 + v*v*(s*t1 - t*s1)*(3*s*s - t*t*N*N)
   v1 = 2*u*v*t1*t**3
   g1 = gcd(s1, t1)
   g2 = gcd(u1, v1)
   return (s1/g1, t1/g1, u1/g2, v1/g2) # don't need last two elements

# Given (x,y) + (x,y) = (s/t, u/v), compute the corresponding alpha = a/d, beta = b/e
def point_to_sides(s, t, N):
   p1 = sqrt(s + t*N)  # sqrt(x+N)
   p2 = sqrt(s - t*N)  # sqrt(x-N)

   a = p1 - p2
   d =  sqrt(t)
   b = p1 + p2
   e  = d
   g1 = gcd(a, d)
   g2 = gcd(b, e)
   return(a/g1, d/g1, b/g2, e/g2)

# test for n congruent when n is odd
def odd(n): 
    cnt1 = 0
    cnt2 = 0
    m = floor(sqrt(n))
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 2*x*x + y*y + 32*z*z == n:
               cnt1 = cnt1 + 1
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 2*x*x + y*y + 8*z*z == n:
               cnt2 = cnt2 + 1
    return(2*cnt1 == cnt2)

# test for n congruent when n is even
def even(n): 
    cnt1 = 0
    cnt2 = 0
    n = n/2
    m = floor(sqrt(n))
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 4*x*x + y*y + 32*z*z == n:
               cnt1 = cnt1 + 1
    for x in range(-m, m+1):
      for y in range(-m, m+1):
        for z in range(-m, m+1):
           if 4*x*x + y*y + 8*z*z == n:
               cnt2 = cnt2 + 1
    return(2*cnt1 == cnt2)

The table through 1000

Here is a table with the side lengths of congruent numbers. Like the web tables, it gives P and Q rather than the side lengths \alpha, \beta, but I give P and Q in factored form. In addition it differs from the web table at N=210, N=559, N=609, and N=985. The changes at N=609 and N=985 give fractions with a smaller denominator. The change at N=559 fixes the glitch wherein both P and Q are both odd.

The change at N=210 adds a second solution with the same denominator. I remarked before that there are multiple values of P, Q (or equivalently \alpha, \beta, \gamma) for each N, and that I would pick the one with the smallest D. This doesn’t always select a unique triangle. For example N=210 has both (\alpha=20, \beta=21, \gamma=29) and (\alpha=12, \beta=35, \gamma=37), both with D=1. Other such examples are

Rendered by QuickLaTeX.com

And now, here’s the table. Also available as a text file.

 
  N                                             P                                             Q
  5                                         5*1^2                                           2^2
  6                                         2*1^2                                           1^2
  7                                           4^2                                           3^2
 13                                        13*5^2                                           6^2
 14                                         2*2^2                                           1^2
 15                                           2^2                                           1^2
 21                                           2^2                                         3*1^2
 22                                         2*5^2                                           7^2
 23                                         156^2                                         133^2
 29                                       29*13^2                                          70^2
 30                                         3*1^2                                         2*1^2
 31                                          40^2                                           9^2
 34                                           3^2                                         2*2^2
 37                                      37*145^2                                          42^2
 38                                        2*25^2                                          17^2
 39                                        13*1^2                                         3*2^2
 41                                           5^2                                           4^2
 46                                         2*6^2                                           7^2
 47                                        3816^2                                        1513^2
 53                                     53*5945^2                                       34034^2
 55                                         5*5^2                                        11*2^2
 61                                      61*445^2                                        3198^2
 62                                       2*140^2                                         151^2
 65                                           3^2                                           2^2
 69                                         3*8^2                                          13^2
 70                                         7*1^2                                         2*1^2
 71                                          60^2                                          11^2
 77                                       11*16^2                                          53^2
 78                                        26*1^2                                           1^2
 79                                       13000^2                                       12921^2
 85                                        85*1^2                                           6^2
 86                                        2*13^2                                           7^2
 87                                         134^2                                          13^2
 93                                          38^2                                         3*5^2
 94                                        2*84^2                                          23^2
 95                                        5*17^2                                        19*2^2
101                                   101*21041^2                                       63050^2
102                                         2*5^2                                           1^2
103                                    93704884^2                                    86901837^2
109                                       109*5^2                                          42^2
110                                        10*1^2                                           1^2
111                                        37*1^2                                         3*2^2
118                                     2*18925^2                                        4393^2
119                                          12^2                                           5^2
127                                 17501923504^2                                 17467450497^2
133                                         506^2                                       19*87^2
134                                      2*1021^2                                         119^2
137                                       137*5^2                                          56^2
138                                         6*2^2                                           1^2
141                                         3*4^2                                           1^2
142                                     2*49590^2                                       12809^2
143                                         318^2                                          43^2
145                                        29*1^2                                         5*2^2
149                                      149*25^2                                         238^2
151                                         340^2                                         189^2
154                                           3^2                                         2*1^2
157                             157*53156661805^2                                407598125202^2
158                                       2*620^2                                         761^2
159                                         182^2                                         107^2
161                                           4^2                                         7*1^2
165                                           4^2                                        11*1^2
166                                      2*9941^2                                        9799^2
167                                      339444^2                                       58717^2
173                              173*3728226965^2                                 48661701478^2
174                                         3*3^2                                         2*1^2
181                                    181*4121^2                                       34950^2
182                                         7*7^2                                         2*3^2
183                                      61*541^2                                       3*390^2
190                                        10*1^2                                           3^2
191                                   636182040^2                                   620449561^2
194                                        97*1^2                                         2*6^2
197                                 197*3179345^2                                    10192154^2
199                                     3732820^2                                      523149^2
205                                         5*3^2                                           2^2
206                                      2*1394^2                                        1103^2
210                                         5*1^2                                         2*1^2
210                                         6*1^2                                           1^2
213                                      3*1600^2                                         851^2
214                                       2*313^2                                         287^2
215                                          62^2                                          19^2
219                                        73*1^2                                         3*4^2
221                                        13*1^2                                           2^2
222                                       74*13^2                                          59^2
223                                  7137389056^2                                  3792733167^2
226                                           9^2                                         2*4^2
229                                   229*61793^2                                       87030^2
230                                        23*7^2                                        2*19^2
231                                         7*1^2                                           2^2
237                                       43454^2                                      3*5915^2
238                                        2*30^2                                          41^2
239                                         120^2                                         119^2
246                                        2*17^2                                          23^2
247                                        5998^2                                        5877^2
253                                         354^2                                       11*91^2
254                                       2*272^2                                         161^2
255                                           4^2                                           1^2
257                                         153^2                                         104^2
262                                      2*7345^2                                        9553^2
263                           49143127346631084^2                           46867792486220437^2
265                                           7^2                                           2^2
269                             269*85656402325^2                                 82710580922^2
271                                   300940360^2                                   101904681^2
277                         277*232579772276105^2                            1032363194300802^2
278                                    2*701185^2                                      990817^2
285                                        19*2^2                                           7^2
286                                        11*1^2                                         2*1^2
287                                      137904^2                                      137903^2
291                                           7^2                                         3*4^2
293                            293*231520447985^2                               3842474897278^2
295                                       5*433^2                                       59*62^2
299                                           6^2                                        13*1^2
301                                        43*8^2                                          27^2
302                                2*2167791890^2                                  3004234751^2
303                                      202046^2                                      166403^2
309                                        3458^2                                       3*799^2
310                                        10*2^2                                           3^2
311                                436723577940^2                                353087218429^2
313                                          13^2                                          12^2
317                              317*2951368765^2                                 16840660634^2
319                                          50^2                                          49^2
323                                        17*5^2                                        19*4^2
326                                     2*33661^2                                         679^2
327                                    109*7969^2                                     3*47950^2
330                                         6*1^2                                         5*1^2
334                                   2*1279626^2                                     1061887^2
335                                        2798^2                                        2629^2
341                                         118^2                                       11*15^2
349                                    349*7453^2                                      113730^2
353                                          17^2                                           8^2
357                                        21*1^2                                           2^2
358                                  2*21866725^2                                    20489063^2
359                                    57470100^2                                    57469741^2
365                                   365*14893^2                                       94874^2
366                                       122*1^2                                          11^2
367                     16382168821648506431464^2                       496953629608513608777^2
371                                        53*1^2                                         7*2^2
373                     373*2603564129117970265^2                        16377382078444972158^2
374                                        2*29^2                                           1^2
381                                         398^2                                       3*221^2
382                                    2*129060^2                                       88679^2
383                                    20091144^2                                    17430983^2
386                                          11^2                                         2*6^2
389                          389*14699193245425^2                              72369303587042^2
390                                         2*2^2                                         5*1^2
391                                         572^2                                         555^2
395                                         5*4^2                                           1^2
397                                  397*109045^2                                     2069034^2
398                                    2*655850^2                                      806831^2
399                                           8^2                                        57*1^2
406                                        58*8^2                                           3^2
407                                    37*11225^2                                    11*20586^2
410                                        41*1^2                                        10*2^2
413                                       64114^2                                     59*6213^2
415                                       29698^2                                       15671^2
421                                421*32786945^2                                   189819882^2
422                                       2*565^2                                         217^2
426                                         6*4^2                                           5^2
429                                         3*2^2                                           1^2
430                                        43*9^2                                        2*41^2
431                                   439631880^2                                    56365561^2
434                                         2*4^2                                        31*1^2
437                                        8914^2                                     19*1247^2
438                                           7^2                                         6*2^2
439                                   266438380^2                                   207471339^2
442                                          11^2                                        26*2^2
445                                        89*1^2                                         5*4^2
446                                  2*37655576^2                                    19427153^2
447                                       22442^2                                       21481^2
453                                     1307114^2                                    3*722785^2
454                                    2*708089^2                                      925711^2
455                                           8^2                                           1^2
457                                         253^2                                         204^2
461                            461*331709140421^2                               6025359571150^2
462                                        14*1^2                                        11*1^2
463                                  1078250296^2                                   376638153^2
465                                           4^2                                        15*1^2
469                                      67*148^2                                        1101^2
470                                        47*1^2                                         2*1^2
471                                     157*949^2                                      3*1962^2
478                             2*7613312866500^2                               1278366247319^2
479                                       46320^2                                       22849^2
485                                    485*6409^2                                       81314^2
487                              31922317361596^2                              20227123841253^2
493                                  493*348125^2                                     3026946^2
494                                       19*11^2                                        2*27^2
501                                      3*8932^2                                        4163^2
502                                  2*13172945^2                                     5749553^2
503                    126022097765194972888404^2                    124468507893835378881997^2
505                                       101*1^2                                         5*2^2
509                                      509*13^2                                         170^2
510                                         2*4^2                                        17*1^2
511                                       18952^2                                        2145^2
514                                       257*1^2                                         2*4^2
517                                           6^2                                        11*1^2
518                                        74*4^2                                          29^2
519                                      570986^2                                       64223^2
526                                      2*3774^2                                         137^2
527                                          24^2                                           7^2
533                                    533*6025^2                                      137522^2
534                                       2*157^2                                         217^2
535                                         418^2                                         311^2
541                             541*82652759501^2                               1629675045390^2
542                             2*8337517165460^2                               6072862516759^2
543                               181*849929197^2                                3*3004968950^2
546                                         7*1^2                                         6*1^2
551                                         350^2                                         179^2
557                              557*1746479765^2                                 40206424678^2
559                                      13*317^2                                      43*174^2
561                                        17*1^2                                           4^2
565                                      565*41^2                                         558^2
566                                   2*3119461^2                                      508681^2
573                                 3*155482680^2                                   222747577^2
574                                        2*12^2                                           1^2
581                                         554^2                                       83*57^2
582                                       194*1^2                                          13^2
583                                     53*8825^2                                    11*19178^2
589                                      19*944^2                                        2265^2
590                                       10*41^2                                          67^2
591                                        1406^2                                         181^2
597                                  4509125978^2                                3*2061246655^2
598                                      26*186^2                                         727^2
599                   1743235759090264843329900^2                   1298070998128102765757269^2
602                                           5^2                                         2*3^2
606                                        3*27^2                                        2*13^2
607         11193477616854092718151692958821016^2          5301570241310268303909957034492887^2
609                                         7*2^2                                           1^2
613                          613*14799287186305^2                              46559016084714^2
614                                  2*59953357^2                                    57198937^2
615                                          22^2                                          19^2
622                                        2*90^2                                          31^2
623                                  3040742304^2                                   958046297^2
629                                       629*1^2                                          10^2
631                              84388339390660^2                              84042085995171^2
638                                     11*2019^2                                      2*4375^2
645                                         5*5^2                                           2^2
646                                         2*3^2                                           1^2
647       1149852430778431376586487272927719076^2        763331759345415695713922022788822893^2
651                                         7*2^2                                         3*1^2
653         653*4956148647851982833406804183365^2           119088454066039826980851213749474^2
654                                      218*13^2                                         121^2
655                                      5*7085^2                                     131*178^2
658                                         2*8^2                                        47*1^2
661                          661*52573871914105^2                            1337443404825678^2
663                                        13*5^2                                        51*2^2
669                                          14^2                                         3*3^2
670                                        67*3^2                                        2*11^2
671                                           6^2                                           5^2
674                                       337*1^2                                        2*12^2
677       677*266071911559565396617913225699185^2          6090385733713292676671917039688234^2
678                                      2*1885^2                                        2567^2
679                                     4829572^2                                     4736355^2
685                                  685*384709^2                                     3760398^2
687                                     229*181^2                                       3*370^2
689                                       689*1^2                                          20^2
694                                       2*269^2                                         329^2
695                                    5*107633^2                                   139*13862^2
701                      701*778126037665372045^2                        20381058964400398922^2
703                                     1176802^2                                      879777^2
709                                      709*17^2                                         210^2
710                                       10*12^2                                          37^2
717                                  3*42438120^2                                      665543^2
718                          2*4524903101629650^2                            2549487886137199^2
719                                       18720^2                                       16511^2
721                                         7*4^2                                           3^2
723                                         103^2                                        3*20^2
727      16213151558097443674133462376327492124^2      11607920028365757398549972945257395957^2
731                                          39^2                                        43*4^2
733            733*7587780721511267936796299165^2              175714842077423718884281543602^2
734                                       2*644^2                                         137^2
741                                           4^2                                         3*1^2
742                                    106*4334^2                                       25983^2
743              664892406397562627531460993684^2               70167984148003728340455310237^2
749                                      107*44^2                                         307^2
751                                         520^2                                         231^2
757 757*134047218103304241673334209140989001305^2    2498951123086366985427431466492641572998^2
758                        2*121343494129262725^2                           13640465896081927^2
759                                         3*2^2                                        11*1^2
761                                      761*29^2                                          40^2
766                                 2*588188916^2                                   153301273^2
767                                    14526198^2                                     3869323^2
773                          773*35770654935185^2                             628933159841954^2
777                                        37*2^2                                         3*3^2
781                                     2079450^2                                   11*578677^2
782                                       2*110^2                                          71^2
789                                     3*53196^2                                       83339^2
790                                       10*88^2                                          39^2
791                                       113*1^2                                         7*4^2
793                                       793*5^2                                         132^2
797 797*6509757429070914743924008309828829377565^2   77437998217120395728776728661988058847754^2
798                                         2*4^2                                           5^2
799                                           8^2                                        17*1^2
805                                           9^2                                         5*4^2
806                                        31*1^2                                         2*3^2
807                                    20388278^2                                     6378229^2
813                                          14^2                                         3*5^2
814                                        74*1^2                                           5^2
815                                    63306722^2                                    60351761^2
821                                     821*905^2                                        6118^2
822                                    2*178445^2                                      221999^2
823    1800731922098507686862624200977450853996^2    1093332003924633933040927920553338780747^2
829               829*1114687145192391935645405^2                  13332313139036257353598962^2
830                                        83*9^2                                        2*29^2
831                                 277*4899877^2                                  3*13289406^2
838                             2*8009381984165^2                               1735885783193^2
839                                      959700^2                                      893651^2
853                        853*1555403055469705^2                           41407411349159166^2
854                                        7*41^2                                        2*27^2
861                                       21*11^2                                          50^2
862                      2*31754083744528352940^2                        44433441426033013319^2
863                      1365999649102602102024^2                      1363371767025194841143^2
866                                          19^2                                         2*6^2
869                                      11*208^2                                         535^2
870                                       145*1^2                                         6*2^2
871                                        3646^2                                        3579^2
877                 877*98019289159914592820005^2                    285144044108203957571958^2
878                                   2*1564070^2                                     2155561^2
879                                          62^2                                          59^2
885                                         632^2                                       59*59^2
886                                   2*1812317^2                                     2229703^2
887          2129987769776435785528571874098484^2           613374508678206671797659663089437^2
889                                           8^2                                         7*3^2
890                                           7^2                                        10*2^2
893                                   314604694^2                                 19*13026563^2
894                                       3*681^2                                        2*73^2
895                                       5*169^2                                      179*22^2
901                                       17*13^2                                        53*4^2
902                                      2*1625^2                                        2297^2
903                                        43*2^2                                         3*1^2
905                                       181*1^2                                         5*6^2
910                                        65*1^2                                        14*2^2
911              101674006024983403715286392160^2              101247414652636878045579297649^2
915                                        61*1^2                                        15*2^2
917                                    79016186^2                                 131*3187071^2
919                                   415257700^2                                   307783011^2
926                           2*207949336647956^2                              65855561465047^2
933                              3*627284421900^2                                906169058509^2
934                                       2*137^2                                          17^2
935                                          52^2                                          47^2
941                           941*6949430837141^2                             212353330183010^2
943                                       41*29^2                                       23*20^2
949                                       949*1^2                                          30^2
951                                          14^2                                          11^2
957                                        29*1^2                                           2^2
958                         2*64137447275611920^2                           86812781740303009^2
959                                          72^2                                          65^2
965                                965*37658777^2                                   268747634^2
966                                        23*1^2                                         2*1^2
967                  40855341363101303203686796^2                  31495021407376795594262853^2
973                                          74^2                                       139*3^2
974                             2*1209837172766^2                                359802927673^2
982                          2*3361484998004965^2                            1361998041016823^2
985                                      985*13^2                                         408^2
987                                        21*4^2                                          17^2
989                                      211066^2                                    43*23387^2
991                                372979863880^2                                355105187961^2
995                                         5*8^2                                          11^2
997 997*205768636979011246293067486487264646177793235665^2 1939472939861978131500861593607331562307144802554^2
998                       2*7036245713483923165^2                         6759000852285855817^2

An incomplete table for 1000 to 2000

One of the motivations for writing the code in this posting was to try computing the side lengths for N > 1000. Of the 358 square-free congruent numbers between 1000 and 2000, the code was able to find sides for all but 50. I’d be thrilled to hear about more sophisticated algorithms that can compute these missing entries.  Here are the entries I was able to compute, also available as a separate file.

 
1003                                    63^2                                 59*4^2
1005                                 5*565^2                                 1202^2
1006                               2*36354^2                                51343^2
1007                             640869638^2                            587562763^2
1013
1015                                 29*13^2                                 35*2^2
1021                           1021*257149^2                              7820010^2
1022                                  2*20^2                                   17^2
1023                                  7664^2                               33*375^2
1030                              103*1327^2                               2*1271^2
1031                       553773154545780^2                      313927967546509^2
1037                            1037*23725^2                               735278^2
1038                                  3*33^2                                 2*23^2
1039                           19222641880^2                            464534841^2
1045                                  5*13^2                                209*2^2
1046                               2*54433^2                                62033^2
1047                            349*815413^2                            3*6269390^2
1054                                2*1692^2                                 1561^2
1055                             5*2218957^2                           211*235258^2
1057                                   247^2                                   96^2
1061                1061*11017137603102721^2                    52393391142142750^2
1063
1069
1070                             107*41187^2                             2*256331^2
1073                                    23^2                                   14^2
1077                                 3*880^2                                 1237^2
1079                                    54^2                                   29^2
1081                                    35^2                                   12^2
1085                                  35*4^2                                   23^2
1086                                 362*1^2                                    1^2
1087           534490229096555257177885984^2          504876251097996356696056863^2
1093
1094                                 2*409^2                                  511^2
1095                                    14^2                                   13^2
1101                                  6734^2                               3*3333^2
1102                             19*330627^2                             2*724355^2
1103                                   816^2                                  287^2
1105                                     7^2                                    6^2
1109
1110                                   2*4^2                                  5*1^2
1111                                    10^2                                    1^2
1113                                   7*2^2                                    5^2
1117
1118                                 26*53^2                                  197^2
1119                           373*5047393^2                           3*56058478^2
1122                                     5^2                                  2*2^2
1126                                 2*953^2                                  113^2
1131                                     4^2                                 13*1^2
1133                                104354^2                             11*31341^2
1135                               4317302^2                              1209899^2
1141                          163*20033248^2                             35220117^2
1142                    2*3498126297122005^2                     3101671470103703^2
1145                                1145*5^2                                   52^2
1146                                  2*13^2                                191*1^2
1149                            3*10180232^2                             17116727^2
1151                             126739920^2                            124197361^2
1154                                    17^2                                 2*12^2
1155                                  11*1^2                                    2^2
1157                     1157*101695523225^2                        1997676115478^2
1158                                 193*5^2                                 6*24^2
1159                                  61*5^2                                 19*6^2
1165                             1165*1037^2                                24366^2
1166                               106*229^2                                  565^2
1167                        80234354894378^2                       69040110896471^2
1169                                  7*12^2                                   29^2
1173                                69*273^2                                 1718^2
1174                         2*10970739277^2                           5524968023^2
1178                                   2*5^2                                 31*1^2
1181
1182                             3*2494283^2                             2*170977^2
1185                                     8^2                                 15*1^2
1186                                   257^2                                2*136^2
1189                               1189*65^2                                 1518^2
1190                                   2*3^2                                 17*1^2
1191                           397*4319701^2                           3*43476026^2
1195                                    22^2                                  5*7^2
1198                         2*79342901670^2                          10971111209^2
1199                            4846487934^2                           4826824675^2
1201                                    25^2                                   24^2
1205                                    31^2                                 5*12^2
1207                              11643884^2                             10025013^2
1213
1214                            2*18094076^2                             12405353^2
1217                               1217*65^2                                 1504^2
1221                                 37*17^2                                33*14^2
1222                                47*151^2                                2*731^2
1223
1229                 1229*3171885776594453^2                    22661957001363890^2
1230                                 123*1^2                                  2*1^2
1231                1093893124029377517040^2                508787759180739534831^2
1237
1238
1239                                   596^2                               177*37^2
1241                                    29^2                                   20^2
1245                                 5*449^2                                  982^2
1246                                  2*24^2                                   23^2
1247                             500503826^2                            493934857^2
1249                                   481^2                                  360^2
1253                            179*139708^2                              1576963^2
1254                                  11*1^2                                  2*2^2
1255                           5*130143077^2                          251*4799482^2
1261                             1261*6205^2                               211494^2
1262     2*5146561601772899976047772998810^2      5187845455908637659823361579711^2
1263                          421*72473677^2                          3*805599790^2
1270                              127*1561^2                               2*5381^2
1271                                  41*5^2                                 31*4^2
1277
1279               73978703287659341689600^2              38338545749238184291809^2
1282                                 641*1^2                                 2*10^2
1285                             1285*1105^2                                 8358^2
1286                      2*10448952878281^2                       10529188863199^2
1293                          3*1697884540^2                           2937063841^2
1294                             2*4872522^2                              1370959^2
1295                                     6^2                                    1^2
1301                 1301*3117192484228345^2                    77237364746203922^2
1302                                    11^2                                  6*4^2
1303
1309                                  77*3^2                                   26^2
1310                             10*153829^2                               432161^2
1311                                  23*1^2                                    2^2
1317
1318                       2*1428058929085^2                         592793094313^2
1319                2483679569975131134420^2               1474854640815874983299^2
1321                                 37669^2                                27060^2
1326                                  26*1^2                                    5^2
1327
1330                                  14*1^2                                  5*1^2
1333                                   206^2                                43*15^2
1334                                 58*48^2                                  133^2
1335                                  4258^2                                 4169^2
1339                                    34^2                                 13*9^2
1342                            11*6293233^2                           2*11110465^2
1343                            1513392816^2                             87126737^2
1346                                   239^2                                2*168^2
1349                          19*572172984^2                           1718426035^2
1351                                    92^2                                193*3^2
1357                             59*799332^2                              6119003^2
1358                                 2*170^2                                  239^2
1365                                   5*2^2                                  7*1^2
1366                      2*75067556653673^2                         276597312593^2
1367             2210029442288216604321564^2            1092492023913676770056123^2
1373
1374                             458*39481^2                               518017^2
1379                                 197*1^2                                  7*2^2
1381                    1381*5877838501505^2                       85358642942118^2
1382
1383                                  8114^2                                 6527^2
1387                                 73*25^2                                19*48^2
1389                              28962134^2                           3*15288133^2
1390                             10*529105^2                              1452477^2
1391                              13*55241^2                            107*14214^2
1393                                  1724^2                               199*57^2
1397                                  11*4^2                                    7^2
1398                                 2*205^2                                   23^2
1399                             140108980^2                             24481971^2
1405                                    19^2                                  5*4^2
1406                                  19*1^2                                  2*3^2
1407                               67*4694^2                               3*9411^2
1411                                    79^2                                 83*4^2
1414                                7*2329^2                               2*4237^2
1415                                  6998^2                                 4451^2
1419                                   3*3^2                                    4^2
1423       7846891217457546585817785748936^2      6692442382211391072755148372327^2
1429
1430                                   2*8^2                                 13*3^2
1434                                  6*10^2                                   19^2
1437                           3*359821900^2                            579736247^2
1438                      2*44553108632760^2                       37487295533089^2
1439             1008014492965566903395280^2             960164863865618935964209^2
1443                                     5^2                                  3*2^2
1446                                  2*11^2                                    1^2
1447
1453
1454                               2*59006^2                                38953^2
1455                                  1586^2                                  263^2
1461                                  9314^2                               3*2233^2
1462                                  34*1^2                                    3^2
1463                                  11*2^2                                 19*1^2
1469                                  13*3^2                                    2^2
1471          1928596035670269313433517160^2         1779886513628987622022447431^2
1477                      211*220919758676^2                        1248458528883^2
1478
1479                                    16^2                                   13^2
1482                                  19*1^2                                  6*1^2
1486                        2*239711193546^2                           8032739393^2
1487                4658308462162163630976^2               1320338709334411132607^2
1493                               1493*25^2                                  434^2
1495                                   202^2                                   87^2
1501                                  19*4^2                                   15^2
1502                          2*2028737420^2                            311366489^2
1509                         3*58309238416^2                           6189441829^2
1510                                  10*4^2                                    3^2
1511                                   780^2                                  731^2
1513                                  89*1^2                                    8^2
1517                                  1181^2                               37*160^2
1518                                   125^2                                22*13^2
1526                                218*16^2                                   19^2
1527                       591153019517366^2                      572357977499363^2
1533                                 28262^2                               3*5805^2
1534                                59*113^2                                 2*29^2
1535                          702318605942^2                         469355582779^2
1541                                    58^2                                 67*7^2
1542                                 2*265^2                                  287^2
1543
1549
1551                                 3*106^2                                11*23^2
1558                               2*24125^2                                20113^2
1559            46558955761464766823805420^2           40991718920623965561016069^2
1561                                   116^2                                223*3^2
1565                               1565*61^2                                 1078^2
1567                                  1624^2                                   57^2
1574
1581                                  93*3^2                                    2^2
1582                                    13^2                                 14*2^2
1583
1589                            1955370754^2                         227*95700609^2
1590                                 265*1^2                                  6*4^2
1591                                    22^2                                   21^2
1595                                   5*2^2                                    3^2
1597
1598                                    39^2                                 94*4^2
1599                                   236^2                                  115^2
1605                                  5*17^2                                   38^2
1606                                2*2269^2                                 1751^2
1607
1610                                  14*1^2                                    3^2
1613
1614                                3*1091^2                               2*1021^2
1615                                85*101^2                                19*42^2
1621
1622
1623                            541*818977^2                            3*8400690^2
1630                                163*81^2                                2*209^2
1631                                    11^2                                  7*4^2
1633                                   324^2                                23*25^2
1635                                 109*1^2                                 15*2^2
1637
1639                           93119931626^2                          17274220825^2
1645                                   381^2                                 5*76^2
1646                               2*10502^2                                12361^2
1649                                1649*1^2                                   40^2
1651                                  13*4^2                                    9^2
1653                                 29*61^2                                  278^2
1654                          2*5099522713^2                           7191812593^2
1655                         5*15944597077^2                       331*1593316982^2
1659                                    10^2                                 21*1^2
1661                          11*449674700^2                           1128819629^2
1662                                 554*1^2                                   23^2
1663
1669                               1669*17^2                                  690^2
1670                                167*41^2                                2*331^2
1671                            4709357954^2                           4709150447^2
1677                                 13*25^2                                129*6^2
1678                    2*2197332480074250^2                     2986757644280911^2
1679                                    83^2                                23*12^2
1685                      1685*10780079129^2                         323265236278^2
1686                               2*30193^2                                 9553^2
1687                        20020795748764^2                       14313931423077^2
1693
1695                                     8^2                                    7^2
1702                           23*83377711^2                          2*259732823^2
1703                          13*136174385^2                         131*42165966^2
1705                                   5*2^2                                 11*1^2
1709                         1709*56899397^2                           1914111430^2
1711                                29*281^2                               59*130^2
1717                                101*13^2                                   38^2
1718                       2*1622842557865^2                         432593825023^2
1726               2*232211988542532693804^2                206435450751981013463^2
1727                               157*265^2                               11*858^2
1731                                 577*1^2                                  3*4^2
1733
1735                               1247378^2                              1029289^2
1741
1742                           67*10122299^2                           2*15946527^2
1743                               3041032^2                            249*85593^2
1745                                 349*1^2                                  5*6^2
1749                                     8^2                                 11*1^2
1751                                  17*4^2                                   13^2
1757                            8065011826^2                        251*412114251^2
1758                        3*102985227451^2                       2*121557212519^2
1759
1762                                 881*1^2                                 2*20^2
1765                          1765*1965793^2                             29034642^2
1766                          2*1241178349^2                            748018649^2
1767                              19*18578^2                              3*43325^2
1770                                   2*4^2                                  3*3^2
1774                                 2*234^2                                  257^2
1781                         1781*64281065^2                           1800656762^2
1783    4792743876089805249498502926760516^2   4210256678211637838081213167457613^2
1785                                   3*2^2                                  5*1^2
1789
1790                             10*178841^2                               493243^2
1794                                  26*1^2                                 23*1^2
1797                          3*5264857000^2                           4228721773^2
1798                           31*10911449^2                            2*7818425^2
1799                                  1740^2                                   59^2
1806                                    47^2                                 6*19^2
1807                             13*408185^2                           139*121818^2
1814                             2*1024057^2                               931217^2
1821                                661934^2                             3*220917^2
1822                               2*17520^2                                23471^2
1823    7761300340225847160065004009945984^2   7073498453526479365692239139413137^2
1829                           59*29844700^2                            181206031^2
1830                                  3*29^2                                122*1^2
1831                            3565715500^2                           2898888171^2
1837
1838               2*640482037573884561770^2                768308549845289572991^2
1839                                613*97^2                                3*294^2
1846                                71*217^2                                2*439^2
1847
1853                       1853*1327014805^2                          56375498794^2
1855                                  1222^2                                  493^2
1858                                    27^2                                 2*10^2
1861
1869                                  21*3^2                                   10^2
1870                                  2*16^2                                 17*1^2
1871
1877
1878                                  2*13^2                                    5^2
1879                            4130777980^2                           1199536101^2
1885                                  29*1^2                                    4^2
1886                                   2*4^2                                    3^2
1887                                  6044^2                                 5119^2
1893                       206546260507082^2                     3*64269514053185^2
1894                        2*324087672709^2                         213795376151^2
1895
1901
1902                        3*900186672163^2                       2*946544303197^2
1903                                114182^2                                19043^2
1909                               4644138^2                             83*21329^2
1910                                  10*6^2                                   13^2
1918                                     9^2                                 14*2^2
1919                               101*197^2                               19*310^2
1927                               1654276^2                               634893^2
1933
1934                              2*127958^2                               180551^2
1939                                 277*1^2                                  7*6^2
1941                      3*22087563983576^2                       35655089110091^2
1942                  2*127615924034303765^2                    89779252381023607^2
1943                              29*16613^2                              67*2990^2
1949
1951
1957                            19*3285772^2                              7471773^2
1958                                  2*15^2                                 89*1^2
1959                        45651794958266^2                       34244727779041^2
1965                                   136^2                               131*11^2
1966                  2*378280891208203374^2                   484645319443334263^2
1967                                 12419^2                               7*4340^2
1973
1974                                  42*2^2                                   11^2
1981                                   506^2                               283*27^2
1982                           2*472837460^2                             48441881^2
1983                                 661*1^2                                 3*10^2
1990                           10*64794470^2                             85105071^2
1991                              181*1193^2                              11*1350^2
1995                                   5*2^2                                    1^2
1995                                   3*2^2                                  7*1^2
1997
1999

Powered by QuickLaTeX