Wrong Mathematics in a Jack Reacher Novel

Lee Child is the author of the popular Jack Reacher thriller novels. He's probably going to get a lot more attention soon, now that the first Jack Reacher movie is headed for release next week.

Five years ago, I discussed some mathematics in Bad Luck and Trouble. I complained that suddenly, a new characteristic of Reacher was unveiled: he was a gifted mental calculator who could determine the primality of numbers quickly, and he was interested in properties like 'square root of n equals sum of n's base-10 digits'.

Now, in the new Reacher novel, A Wanted Man, Child returns to this numerological interest of his main character. First, Reacher is thinking about automorphic numbers: these are positive integers n such that n² ends in the same base-10 digits as n.

Then (on page 64), Reacher is thinking about 81, and he "muse[s] about how one divided by 81 expressed as a decimal came out as .0123456789, which then recurred literally forever, 0123456789 over and over and over again..."

The problem? That's not the decimal expansion of 1/81. It's actually 0.012345679012345679012345679012345679012345679012345679012345679 ..., where the period of the expansion is 012345679 and not 0123456789. The "8" is missing! The reason for this is not so surprising, and generalizes easily to the expansion of 1/(n - 1)² in base n.

A savant like Reacher, who can determine the closest prime to a randomly-chosen 6-digit number in a matter of a few seconds, would not have made such a silly mistake. Maybe Lee Child needs a mathematical consultant for his next novel. Hey, I'm available.

Mathematics Journal gets Sokaled

Over at That's Mathematics, the author reports that his paper of gibberish mathematics was actually accepted by the journal Advances in Pure Mathematics. This gives you some idea of the quality of that journal.

The paper contains such deathless phrases as "By a little-known result of Fibonacci..." and "It is not yet known whether every real, surjective, pairwise regular functor is ultra-standard". The author pairings in the bibliography include Atiyah and Leibniz, and Atiyah and Eudoxus. Very nice work.

An Interesting but Little-Known Function

A boolean matrix is a matrix whose entries are truth values, usually represented as 1 (true) and 0 (false). We multiply boolean matrices in the same way that we multiply ordinary matrices, except that instead of sum we use the boolean "or" and instead of product we use the boolean "and".

Boolean matrices have a natural interpretation in terms of directed graphs: given a graph G on n vertices, we put a 1 in row i and column j of M if there is a directed edge in G from vertex i to vertex j, and 0 otherwise. Then the boolean matrix power M^e has a 1 in row i and column j if and only if there is a directed path from vertex i to vertex j of length e.

Given an n × n boolean matrix M, a natural question is, what is the largest size s(n) of the semigroup generated by M under boolean matrix multiplication? In other words, how many distinct powers can M have, in the worst case? Believe it or not, this natural quantity has received very little attention in the literature. There is a paper by Markowsky in 1977, and another by Denes, Roush, and Kim in 1983, but that's about it. For small n, it is known that s(n) = n² - n + 2, while for larger n, it is known that s(n) is approximately g(n), Landau's function, which counts the maximal order of an element in the symmetric group of order n. It is known that Landau's function is approximately e^{sqrt(n log n)}, so this tells us how s(n) behaves for large n. But to my knowledge nobody knows the exact value, or even small values past n = 20. This might be a nice computational challenge for an undergraduate.

Too Bad This Guy Isn't a Mathematician

The guy at the city of Waterloo, Ontario who helped the mayor of Waterloo get online at the "Chinese Facebook", Sina Weibo, is named Max Min.

What a great name! Too bad he isn't a mathematician.

What's Norwegian and Commutes?

Why, an Abelian plane, of course!

Norwegian Airlines has pictures of famous Scandinavians on the tails of their planes, including the mathematician Niels Henrik Abel (1802-1829). You can see some of the other ones here. Oddly enough, the Norwegian Air website itself only lists a few of them.

Strangest Textbook Title

There are a lot of strange textbook titles, but this one may be the strangest of all:

Discrete Mathematics with Ducks.

That's just silly! Everybody knows that you do discrete mathematics with geese, not ducks.

A Functional Equation

You might know the gamma function, which is one way to extend the factorial function to the complex plane. It obeys the functional equation

Γ(1) = 1

Γ(z + 1) = z Γ(z).

In fact, if we demand that it be logarithmically convex and obey the rules above, then the ordinary gamma function is in fact the only way to extend the factorial function to the positive reals. (Here Γ(n) = (n-1)!.)

Now the successor function z → z + 1 is on the lowest level of the Grzegorczyk hierarchy. The next higher level includes the function z → 2z. So, in analogy with gamma function, suppose we demand that

f(1) = 1

f(2z) = z f(z).

Then what's a "reasonable" function that satisfies this functional equation? My answer in the comments tomorrow, unless someone comes up with the same answer I did.

Avoiding Sum Cubes

One of the most interesting and challenging open problems in combinatorics on words is to decide whether there exists an infinite word over a finite subset of N, the non-negative integers, with the property that it contains no two consecutive blocks of the same length and the same sum (a "sum square").

For example, 01231301020103102310313231301020131013230 is a word of length 41 with this property, but if you append any one of {0,1,2,3} to it, it no longer does. Appending 0 gives the sum square 00; appending 1 gives the sum square (3231301020)(1310132301); appending 2 gives the sum square (103132313010)(201310132302); appending 3 gives the sum square (132)(303). So this word cannot be extended to an infinite word avoiding sum squares; the longest such is of length 50. Of course, there could be an infinite word avoiding sum squares over some other subset of N; no one currently knows.

This problem was originally stated by Pirillo and Varricchio in 1994, and independently by Halbeisen and Hungerbühler in 2000.

Today we posted a preprint in the arxiv that solves a related unsolved problem. Instead of avoiding sum squares, we show that we can avoid sum cubes: three consecutive blocks of the same length and same sum.

The construction is actually quite simple: the infinite word in question is the fixed point of the morphism
0 → 03
1 → 43
3 → 1
4 → 01,
and can be obtained by repeatedly applying this morphism starting with 0. Here are the first 50 terms:
03143011034343031011011031430343430343430314301103 .
I found this morphism several years ago.

However, proving that this word has the desired property is not simple. The proof was recently achieved by Luke Schaeffer, using ideas of James Currie at the University of Winnipeg and Julien Cassaigne at the Institute de Mathématiques at Luminy in France.

My Talk for the Wilf Conference

Laurier (the other university in Waterloo, Ontario) is hosting a conference this May 26-29 in honor of Herb Wilf's 80th birthday. Wilf (b. June 13 1931) is a very influential mathematician, known for his work on combinatorics and combinatorial algorithms. He also founded the Electronic Journal of Combinatorics.

Of course, it's better in person, but if you can't make my talk at 10:40 AM on May 27 2011 in Room N 1001, Faculty of Science Building, WLU, then you can see the slides here.

Catenaries on "Car Talk"

Here's a puzzle from the radio show, Car Talk, with the misspelling corrected:

"There are two telephone poles. Each one is 100-feet tall. They are parallel and an unknown distance apart.

"We're going to attach a 150-foot rope from the very top of one of the poles to the top of the other. This rope will, of course, droop down somewhat. That drooping rope is called a catenary, from the Latin word for chain.

"The question is: What must be the distance between the two poles, so that the lowest point of the catenary is 25-feet above the ground?"

I confess, I worked out the equation for a catenary to try to answer this, but that's a waste of time if you think about the problem a little.

The answer, if you need it, is here.

Can Irrational Numbers be Represented in a Computer?

I often see the following claim, or variants of it:

"In a computer (as we understand computers, at least), irrational numbers can't be fully accurately represented."

This one happens to be from Bradley Monton, Seeking God in Science: An Atheist Defends Intelligent Design, Broadview Press, 2009, p. 128, but Monton isn't alone.

This is a common misunderstanding that, I think, has two bases. First, for people without much mathematical training, a real number is inextricably linked with its base-10 (or perhaps base-2) representation. For them, the number π is 3.141592653 ..., as opposed to being defined by an integral or infinite series. Second, people without computational training often don't understand that some infinite objects -- including some base-10 or base-2 representations of irrational real numbers -- are routinely represented as finite objects in computers.

Let's take √2 as an example. Although it is irrational, symbolic algebra systems such as Maple and Mathematica routinely represent √2 "exactly" and allow manipulations with it. For example, if you type

> x := sqrt(2);
> x^2;

into Maple, it will happily return the "exact" answer 2. And, similarly, other arithmetic operations involving √2 will give the "exact" answers:

> expand((123+45*sqrt(2))^3);

3355317 + 2224665 √2;

Similarly, we can manipulate other famous irrational numbers such as e, π, etc, and often get "exact" results. The point is that many of the irrational numbers that people actually care about need not be stored in terms of their base-10 or base-2 representation.

But even if we insist that yes, they must be stored in this way, there can still be finite representations. For example, consider the base-10 number defined by having a "1" in the i'th digit if i is a perfect square (like 1,4,9,16, etc.), and 0 otherwise. Now it is easy to see that this number is irrational. But we can still store it in a finite way (for example, as a function that returns the i'th digit on input i), and do at least some simple manipulations on this representation. For numbers whose base-k representation is encoded by a finite automaton, for example, we can do addition, even if the carries come from "infinitely far" to the right. (This is not trivial.)

In fact, any algebraic number, and many others, can be stored as a finite program that on input i returns the i'th digit. In some cases we can even do this by a very simple recurrence. For example, Graham and Pollak, in a 1970 paper, gave a simple explicit recursion to compute the i'th bit of √2 .

The misguided claim I started with can be fixed. If instead we say, "The base-2 representation of most irrational real numbers is not compressible to a finite representation, so the entire base-2 representation of most irrational real numbers cannot be stored in a finite computer", we would be correct. Here "most" means "all but a set of measure zero". But this is not particularly interesting, since for actual computation we are rarely interested in "most" irrational numbers -- we are interested in the computable ones.

William Lane Craig Does Mathematics

In his debate with Lawrence Krauss last night (audio here), William Lane Craig says,

"But mathematicians recognize that the existence of an actually infinite number of things leads to self-contradictions. For example, what is infinity minus infinity? Mathematically, you get self-contradictory answers."

It's hard to know what Craig really means here, because it is so confused. Mathematicians routinely study "an actually infinite number of things", such as the natural numbers, the real numbers, and the complex numbers. No contradictions are involved.

But maybe Craig is talking about an actual infinity of things in nature. Then he shouldn't be talking about mathematicians, but physicists. Even here, physicists do discuss an actual physical infinity - without contradictions - such as Malament-Hogarth spacetime. Examples like Hilbert's hotel, that are often proffered as insoluble paradoxes, only show that infinity needs to be treated with care and may result in scenarios that seem counter-intuitive. But so does relativity.

Infinity minus infinity is not "self-contradictory", any more than 1/0 is "self-contradictory". Lane seems not to understand that not all functions are everywhere defined. The subtraction function, for example, can be defined on most pairs of the extended reals, but not defined on (∞, ∞). What's so hard to understand about that?

Addendum As I listen to more of the debate, it seems Craig retreats a bit from his claim about mathematics. He still seems to think that an actual infinite number of objects in the universe creates "contradictions", but he doesn't say explicitly what those contradictions are.

"Any" Considered Harmful

Edsger Dijkstra wrote a famous letter in the Communications of the ACM that appeared under the heading "Go To Statement Considered Harmful".

I'd like to make a case against the use of "any" in mathematical discourse.

The problem with "any" is that it can mean both "for all" and "there exists", and it's not always clear what is meant. "It's true for any x" probably means "for all x". But "The theorem is true for S if any element of S is a square" probably means "it's true if S contains at least one square".

I was just attending a meeting at Dagstuhl in Germany where one speaker said something like "If L is regular, then u is equivalent to v if and only if for any state q of the minimal DFA for L we have δ(q,u) = δ(q,v)". Now if you know the theorem, the meaning is clear. But if you don't, you might be left wondering, does he mean "u is equivalent to v if there exists some state q such that δ(q,u) = δ(q,v)" or "u is equivalent to v if for all states q we have δ(q,u) = δ(q,v)"?

Because of this ambiguity, I think we should avoid the use of "any" in mathematical discourse. We can replace it by "all x" or by "some x", according to what we mean.

Who's with me?

Fibonacci Quarterly Goes Electronic

The Fibonacci Quarterly has gone electronic! And they've put all their articles before 2006 online for free.

When I was a teenager, this was one of my favorite journals - because, unlike most math journals, I could actually understand most of the articles in it. My parents thought it was weird, but they were very understanding, and even got me a subscription.

I remember one of the articles that blew my mind was Aho and Sloane's Some Doubly Exponential Sequences. The authors found beautiful analyses of some nonlinear recurrences, including one of my favorites:

y₁ = 5; y_n+1 = (y_n - 2)².

The first few values are y₂ = 9; y₃ = 49; y₄ = 2209; and it is not hard to prove that y_n = L_2ⁿ + 2, where L_i is the i'th Lucas number.

It's still a good and worthwhile journal, even if it doesn't usually get much praise from the kind of people who publish in Inventiones. It struggles from time to time with quality issues, and I really dislike the typesetting, but there's often something interesting in it.

So, congrats to the Fibonacci Quarterly for taking this step. If only they'd put in a search function for titles and authors...

Naming Infinity

Loren Graham, an American historian of science, and Jean-Michel Kantor, a French mathematician, have collaborated on a recent book, Naming Infinity: A True Story of Religious Mysticism and Mathematical Creativity (Harvard University Press, 2009).

Graham and Kantor's thesis is that a Russian religious cult, "name worshipping", was partly responsible for advances in set theory made by Russian mathematicians in the early 1900's, whereas the French "rationalistic, Cartesian" approach prevented similar breakthroughs. Indeed, on p. 189 they claim "under the influence of their [Borel, Baire, Lebesgue's] ultra-rationalistic traditions, they lost their nerve". (However, this supposed "loss of nerve" is not supported by any documentation.)

I found it an interesting book, but one that did not successfully support its thesis. After all, placing the responsibility for an historical event on some other single event or belief is highly problematic: consider that there are still people who debate the conclusion that slavery was a primary cause of the American civil war. Why one group solved a mathematical problem, while another failed, is not always so simple to determine. It can be a matter of pure intellectual ability, or a desire to focus on one area rather than other, or something entirely random, like a conversation in a café. Graham and Kantor hedge a bit on p. 100, where they write, "when we emphasize the importance of Name Worshipping to men like Luzin, Egorov, and Florensky, we are not claiming a unique or necessary relationship. We are simply saying that in the cases of these thinkers, a religious heresy being talked about at the time when creative work was being done in set theory played a role in their conceptions. It could have happened another way; but it did not." But if this all they were saying, then so what?

Srinivasan Ramanujan believed that his family's deity, Namagiri, whispered equations in his ear. But it doesn't necessarily follow that without a belief in Namagiri, he would not have created the mathematics he did. Maybe he would have been an even better mathematician had he not been imbued with his Hindu superstitions.

Similarly, it's not clear to me that Russian mathematicians like Egorov, Luzin, Florensky, and others could not have been just as successful -- or even more so -- had they not subscribed to their bizarre Christian cult. It even seems that their cult could induce ridiculous statements like the one the quote from Bely: "When I name an object with a word, I thereby assert its existence." That will certainly be news to unicorns and the set of all sets. Similarly, Luzin wrote that he "consider[ed] the totality of all natural numbers objectively existing" (italics in original), which raises the question, what precisely does it mean for a number to "exist"? This point is not really discussed by the authors. But it seems to me that, for example, that the number ℵ₀ "exists" in exactly the same way that the number 4 "exists".

The book is generally well-presented, although I found a couple of things to quibble about. On page 58, for example, the authors claim that "explicit namings of even one of them [normal numbers in base 10] have been very difficult to obtain". But this is not true. For example, Champernowne's number .123456789101112 ..., which consists of the decimal expansions of the integers concatenated in increasing order, has a very simple proof of normality found by Pillai in 1939. Many, many other examples are known, such as the result of Davenport and Erdős in 1952 that .f(1)f(2)f(3)... is normal if f is any polynomial taking positive integer values at the positive integers. And I was also annoyed by the misspelling "Riemanian surfaces" on p. 113 --- "Riemann" has two n's, not one --- and the failure to put the proper accents on Wacław Sierpiński on p. 118.

Nevertheless, this is a little book worth reading, even if its main thesis is poorly supported. For me, the best part of the book was the history of Soviet mathematics in Chapters 7 and 8. Although I knew the names of most of the Russian mathematicians discussed, I had not explicitly realized the extent of mathematical talent in Moscow in the 1920's. And the mistreatment of Egorov, Luzin, and Florensky under Communism, and the bravery of people like Chebotaryov who stood up for them and suffered as a result, is a cautionary tale worth knowing about.

Call For Papers: Special Issue in Honor of Alf van der Poorten

Call for papers: A special issue of Journal of the Australian Mathematical Society dedicated to Alf van der Poorten.

We solicit submissions in all areas of mathematics, and especially in the areas close to the research interests of Alf van der Poorten (e.g., recurrence sequences, continued fractions, diophantine approximation, and p-adic numbers). The submission deadline is 1 May 2011. We hope to have all submissions evaluated and make the acceptance/rejection decision by th end of October 2011 with the goal to have this issue to appear early 2012.

Please direct all submissions to Igor Shparlinski.

The Editors
Francesco Pappalardi
Igor Shparlinski
Jeffrey Shallit

A Mathematico-Religious Poem

Here's a poem by Hooper Reynolds Goodwin that was published in the journal Scripta Mathematica in 1953. I liked it very much when I was a teenager, and I still think the last two lines are excellent.

PARABOLA

This curve I'm plotting? A parabola.
This point is called the focus; it's the point—
Oh, no, not an ellipse. Ellipses have two foci:
Here, I'll show you one I've drawn.
You see the difference. These two lines of the parabola,
They stretch out wide and wider,
"World without end," as preachers say.
(I don't know what they mean; perhaps they don't);
But you see how it goes.

There was a man—Sir Isaac Newton, I believe it was—
Who had the notion a parabola was an ellipse,
Its other focus at infinity.
You may not understand just what he meant;
You have to sort of take the thing on faith.
The keenest scholar can't quite picture it, you know.

I've often thought,
It might be called a symbol of man's life;
A curve of ever-widening sweep.
And here in this world
Is the focus we may call, say, temporal interests,
Food and drink and clothes . . .
But yet it cannot be that this is all;
For out beyond the reach of sight must be
Another point, a heavenly focus, see?
'Round which the sweeping curves of human life
Complete the ellipse.
Fantastic? Well, perhaps,
But yet the more I think of it...

And here—
Another thing I've often thought about:
Suppose we draw here two parabolas
With axes parallel, and let the arms cross—
"Intersect" the word is—at this point.
Now if there be a focus
Somewhere out beyond the bounds of space,
And these are two ellipses,
As Sir Isaac thought they were,
Why, don't you see, they'll intersect again
Somewhere out there.
Just as two lives that once have crossed,
Then gone their separate ways,
And one has disappeared long since into the void of death
May—but who knows? It's just a thought...

Well, come again; I don't get callers often.
They don't see much in old folks nowadays,
And when a man's not only old, but got his head
Stuck always in a book of "AnaIyt!"
Young people think I'm queer; they can't see why
A man that doesn't have to study graphs
Should plague his head; don't understand that such
Dry, dull things as a parabolic curve
May bring up mem'ries of a face that's gone.

---

The author, Hooper Reynolds Goodwin (December 5 1891-October 13 1964), was born in Marblehead, Massachusetts. Raised by Unitarians, he attended Boston University and was ordained as a Methodist minister. Later he became an Episcopalian minister. He served in churches in Bethel and Randolph, Vermont.

I am very grateful to his granddaughter, Sue Maltais, for providing a photo and information about his life.

Oberwolfach!

Oberwolfach!

For mathematicians, it's a little bit like Mecca for Muslims: everybody wants to go at least once in their lifetime.

I first heard about Oberwolfach when I was an undergraduate. My first significant paper had finally appeared in the Journal of Number Theory after a very long delay (that's another story), and I sent it off to some mathematicians I thought would be interested. One replied, "But I just heard Schinzel talk about this at Oberwolfach..." I had been scooped! During the long delay in publication, a Czech graduate student studying in Poland had found the same result. And what was Oberwolfach?

It's a research center and conference site. Nowadays there are several similar places, such as the Banff International Research Station and the Centre International de Rencontres Mathématiques, but Oberwolfach is the oldest and most famous. (There's a history of the place here.)

For those who are not familiar with what happens at a place like Oberwolfach, here's a brief account. For 50 out of 52 weeks of the year (the exceptions being Christmas and New Year's), the Institute is host to about 50 mathematicians who arrive from Germany, the rest of Europe, and around the world. Each Sunday, they typically arrive by train at either Hausach or Wolfach, two small towns in a river valley in mountainous southern Germany. From there they take a taxi to the Institute, which is located on a remote tree-covered hillside that's a good 5 km from the nearest town.

There are two main buildings. One houses the dormitory and cafeteria, the other the library and conference rooms. Oberwolfach provides three meals a day; at lunch and dinner there is assigned seating, which changes at each meal. The main work takes places Monday through Friday, and usually consists of some talks (we had about 4 hours each day) and working on problems in small groups (all the rest of the day and night). There are numerous coffee machines (Paul Erdős supposedly once said that "A mathematician is a machine for turning coffee into theorems", although it has also been attributed to Rényi), where espresso and café au lait can be had, gratis, at all hours. Drinks, both alcoholic and non, can be bought for very nominal prices. The picture below shows the result after a long night of drinking and mathematics.



The dormitory rooms are very spartan, with no decorations and no TV, radio, or phone. Although there is some wireless internet available in both buildings, most dormitory rooms do not have access. You're supposed to be talking to other mathematicians, not sitting in your room!

I was there for a "mini-workshop" on Combinatorics on Words. We had 17 participants, and there were two other workshops running concurrently. This differs from most weeks, which are typically devoted to a single theme and involve more participants.

Oberwolfach also offers other kinds of programs, such as "Research in Pairs", which allow two mathematicians from different institutions to meet and work together for a longer period.

The library is really outstanding. Unlike many libraries, they have not switched to electronic subscription, and they continue to receive paper copies of journals. It is a real pleasure to walk down the long aisle and pick up a journal to browse. Although I thought I knew the mathematical literature reasonably well, there were still some journals I had never heard of.



Oberwolfach also has a tradition of putting books written by participants on a special shelf in the library building. You can see my book displayed there below.



Another Oberwolfach tradition are the problem books. Any mathematician can provide an unsolved problem, or comment on a previous one, and there are dozens of problems by famous mathematicians like Erdős. Here's a page from the problems book with a problem by Mendès France:



On Saturday, all the mathematicians leave in taxis arranged by the Institute. And on Sunday the cycle begins again.

I had a really great experience there. There were some excellent talks by my colleagues, and I got a chance to discuss some open problems with them. We even solved one problem, and made some progress on others. I'm hoping to go again some day!

Some Unimpressive Numerology

The fine-structure constant α is a fundamental constant in physics, and is currently estimated to be approximately .0072973525376.

The physicist Arthur Eddington, who became rather eccentric and believed he could compute the number of protons in the universe accurately, thought it was equal to exactly 1/137, but our current estimate gives something closer to 1/137.03599967899.

The mathematician James Gilson seems to think that α is given by the rather complicated formula (29/π)*cos(π/137)*tan(π/(137*29)). But this is just numerology, and not even particularly impressive numerology. The trick is that tan(x) is very close to x when x is small, and cos(x) is very close to 1 when x is small. So Gilson's formula is just (29/π) times something that is very close to π/(137*29), with an additional fudge factor of something that's very close to 1 thrown in. There is no real surprise, then, that one can find small integers to make this close to α.

Heck, it's obvious that the real value of the fine structure constant is actually 250/34259. Or maybe (cos(2 π/57) - sin(4 π/47))/100? I can't decide which.

How to Test for Syphilis

Yesterday on NPR's "All Things Considered" I heard this segment about "sparsity", which tried to link several different issues about data compression in one story. I don't think it was very successful, and the chosen term "sparsity" wasn't really representative of the content.

Nevertheless, the piece opened up with an interesting puzzle. The Army wants to do comprehensive blood tests for syphilis, a relatively rare disease, but each individual test is expensive. How can they test everyone more cheaply?

The idea is simple: mix the blood of g individuals together, and test that. A positive outcome indicates that at least one person in the group has syphilis, and a negative outcome indicates that no person in the group has it. In the event of a positive outcome, test all the members of the group.

Now let p be the probability that a randomly-chosen person has syphilis, and let N be the population size. What is the optimal size for the group? Choose g too small, and you end up doing lots of tests, because N/g (the number of groups) is large. Choose g too large, and it becomes very likely that testing the group will be positive, so you end up doing lots of tests again. Somewhere in between is the optimal choice of g.

How do we find it? There are N/g groups, and we have to test each of them. A randomly-chosen person fails to have syphilis with probability 1-p, so the probability that everyone in the group fails to have it is (1-p)^g. Hence the probability that a group tests positive is 1-(1-p)^g, and the expected number of positive-testing groups is (N/g)(1-(1-p)^g). We have to test each person in a positive group, so this means g(N/g)(1-(1-p)^g) = N(1-(1-p)^g) additional tests. If the cost of a test is C, then the total cost is CN/g (the cost to test each group), plus CN(1-(1-p)^g) (the cost to test everyone in the positive-testing groups). Factoring out CN, we need to minimize

1/g + 1 - (1-p)^g.       (1)

Notice that this expression only depends on p, the probability.

We can, in fact, find a closed form for this minimum (or at least Maple can), but it is somewhat complicated, and depends on the little-known Lambert W-function. It's easier to compute the minimum through bisection or some other method for any particular p. A recent estimate is that syphilis occurs in about 15.4 per 100,000 people, which corresponds to p = .000154. For this value of p, the optimal g is g = 81, which gives (1) the value of .0247. Thus, for this p, we are able to test everyone by combining tests -- for less than 3% of the cost of testing everyone individually.

By the way, a simple heuristic argument suggests that the g that minimizes (1) will be about p^-½: to minimize (1), choose g so that the two terms in the sum (1), 1/g and 1-(1-p)^g, are equal. Set g = p^-½; then 1/g = p^½. On the other hand, 1-(1-p)^g = 1 - (1-g^-2)^g. But (1-1/g)^g is about 1/e for large g, so using the Taylor series for exp(x), we see that 1 - (1-g^-2)^g is about 1/g, too. So this choice of g will be very close to the one minimizing (1), and the value of (1) is therefore about 2/g = 2 p^½.

Added: with more complicated tests (see the comments), one can do even better. But some of the proposed methods are so complicated that it seems to me the possibility of human error in carrying them out would rule them out.