Fermat's Little Theorem, Euler's Generalization and Artin Representations

I know I haven't been blogging for a while, but I'm happy to give a brief update here of why I haven't along with some fun number theory.

There's a well-known theorem, likely familiar to all the mathematicians who might read this blog, known as Fermat's Little Theorem. This theorem should not be confused with Fermat's Last Theorem which is much harder to prove and of much less general mathematical interest aside from the historical importance.

Fermat's Little Theorem says the following: Suppose you have a prime p and suppose you have a positive integer a that is not divisible by p. Then a^(p-1) leaves a remainder of 1 when divided by p (or as mathematicians like to say, a^(p-1) = 1 (mod p). Here the notation x=y (mod n) means that x and y have the same remainder when we divide by n.  So for example, 3^4=81 which leaves a remainder of 1 when I divide by 5.

Euler generalized this result so that p=n did not need to be prime. But to do that one needs to do a few things. First, one needs to strengthen the condition on a. So instead of n not dividing a, one wants that a and n have greatest common divisor 1. Second, instead of (n-1) in the exponent of a, one needs φ(n), where φ(n) is what is called the Euler phi function. This function counts how many positive integers are less than or equal to and relatively prime to n. For example, φ(6)=2 because the only such integers are 1 and 5. Then we have the theorem that if a and n are relatively prime then a^φ(n) = 1 (1 mod n).

Now, why am I thinking about this result? Well, one can for a fixed a and a given n, ask what the actual lowest power one needs to raise a to get something that is 1 mod n. So for example, for 7, φ(7)=6, but if one looks at 2, one will see that one can take 2^3=7+1, so 2 in this case didn't need as high a power as it might otherwise need. Let's write ord_a(n) to be this minimum power. There's been a lot of work in the last hundred years in trying to understand this function and related behavior.

One natural thing to do is to look at the average of value of phi(n)/ord_a(n) That is, for any x, look at G(x)= Σ  φ(n)/ord_a(n) where the sum is over all n that are relatively prime n and less than or equal to x. So what can we say about this function? Lower bounds were recently proven by Christopher Ambrose,  who showed that for any a, the G(x) grows slightly faster than x^1.7 (here the actual constant is an ugly irrational). There's also an easy upper bound, but until recently no non-trivial upper bound was known. I'm please to say that that is now known. In particular, for any α less than 3, it is now known that G(x)=O(x^2 / (log x)^α). A draft of that paper can be found here. So, now you know part of what I've been working on for a while now and why I haven't had as much time to blog.  The result in question is actually secondary to the main theorem about counting what are called Artin Represenations (or in the restricted case I care about, actually ray class characters), which I hope to discuss in a future blog entry.

Correlation coefficients as angles

Harry Altman has an interesting piece over at Less Wrong suggesting that it makes more sense to think of correlation coefficients as angles. To many people a correlation coefficient is nothing more than a number between -1 and 1 which shows in some easy to quantify but hard to intuit way of how related two variables are. Harry's suggestion gives a useful way of thinking about them and is worth a read. 

Conservatism, racism, and stupidity

A recent study  argues that there is  a correlation between racism, political conservativism, and stupidity. More intriguingly, the study claims that this is not just a correlation but an actual causal link, with the third causing the other two.  The study is not at all persuasive.
Not surprisingly, this sort of thing produces a fair bit of discord. From the abstract:

 We proposed and tested mediation models in which lower cognitive ability predicts greater prejudice, an effect mediated through the endorsement of right-wing ideologies (social conservatism, right-wing authoritarianism) and low levels of contact with out-groups. In an analysis of two large-scale, nationally representative United Kingdom data sets (N = 15,874), we found that lower general intelligence (g) in childhood predicts greater racism in adulthood, and this effect was largely mediated via conservative ideology. A secondary analysis of a U.S. data set confirmed a predictive effect of poor abstract-reasoning skills on antihomosexual prejudice, a relation partially mediated by both authoritarianism and low levels of intergroup contact. All analyses controlled for education and socioeconomic status. Our results suggest that cognitive abilities play a critical, albeit underappreciated, role in prejudice. Consequently, we recommend a heightened focus on cognitive ability in research on prejudice and a better integration of cognitive ability into prejudice models.

While the claimed result is fairly moderate, bloggers on the left end of the political spectrum quickly jumped on the study, with one stating:

Wait a minute.  You’re saying the people who almost all believe a Canaanite Jew rose from the dead 2,000 years ago, who deny global warming, who deny evolution, the people who think losing in court is a better use of money than education, who think letting people love who they wish is destroying America, who think not educating children about sex prevents pregnancy or disease…the study concludes that those people tend to be dumb?

Many simiar comments  ignored the fact that the main part of the study took place in the United Kingdom while the traits mentioned above tend to be more highly associated with American conservatives. This isn't too surprising since few people actually linked to the actual study but apparently got their information from secondary news sources.

Commentators elsewhere on the political spectrum have not been much better, dismissing the study as more liberal propaganda rather than actually addresssing the questions that the study raises.
One of the most substantive responses came from William Briggs. Judging from Briggs's remarks he has over advantage over many of the commentators: he has apparently read the study in question. While most of Briggs's criticism is superficial, minor or unfair, he does have some valid points.

Briggs's first criticism is that only parts of the intelligence test data was used. He is correct to note this. The apparent implication is that the omitted data would if included undermine the claim in question.  While it might be interesting to look at that omitted data, there is a prosaic explanation for the exclusion of this data: The removed tests are for aspects of reading and math ability which are more function of education and background, and are not as useful indicators of actual cognitive ability.

Briggs also criticizes as badly phrased the questions used to measure social conservativism:

When the kids became 33 and 30 year olds, they were asked whether they agreed with 13 or 16 questions like, “Schools should teach children to obey authority”, “Family life suffers if mum is working full-time.”

Another was, “People who break the law should be rehabilitated.” Just kidding! It’s actually, “People who break the law should be given stiffer sentences.” The bias in the question wording is ignored.

There's such as a thing as the framing effect, where the  phrasing a question can influence how people will answer the question. However, in this particular case, neither question seems obviously more biased to me. Moreover, even if there is some form of  framing effect here, that should alter the overall percentage who answer one way or another, there's no reason it should impact whether conservatism and intelligence will be correlated. If any readers can construct a hypothesis about how framing would have a disparate impact, I'd be very interested in hearing it.

Briggs also complains that the intelligence measure used a latent variable, g, for which he felt a need to put in scare quotes.  While Briggs might be unhappy with such a variable, the existence of a general fluid intelligence is well documented, going back to Charles Spearman's work around a hundred years ago. Psychometricians have a good understanding of how g and similar variables behave. While the g here is not precisely identical to Spearman's g, the existence of such an underlying factor is essentially uncontroversial.

By far the best criticism that Briggs makes is to question whether the results are genuinely statistically significant. There are some subtleties with whether their p values are correct, and Briggs is correct to note potential issues there. However, the real problem is as Briggs observes, that the actual impact of intelligence on the issues in question is tiny.

What Briggs does not discuss in detail  is that the second part of the study, which analyzes  attitudes towards gays and intelligence levels in the US sample, showed a much stronger and more clear correlation between intelligence and attitude. The data for the attitudes towards gays isn't  original to this paper but comes from a previous paper by a different author which showed a correlated between intelligence and greater acceptance of gays. While this paper does try to construct a  causal model, the model is complicated and not convincing. However, the weak nature of their model doesn't reduce the fact that the prior paper's data is quite strong.

Despite all this, I think that the conclusion that, within the US self-identified liberals are on average smarter than self-identified conservatives is correct. That conclusion has nothing to do with these two papers but is based on other sources. The General Social Survey shows a strong correlation between larger vocabulary (which is highly correlated wit a variety of intelligence metrics) and liberalism. The actual pattern in the GSS data is actually a bit more subtle:  smarter people are in general more likely to have extreme political views than dumber people, and smarter people more likely to have liberal views. Essentially, as  intelligence increases, the distribution of political opininon becomes more bimodal and moves to the left.  This is part of a general pattern in the US that I've discussed  before - moderates are stupid and ignorant. The GSS isn't the only place one sees these twin patterns.

However, neither of these two trends is strong. Both these trends occur in large samples. They are true only on average. At an individual level, the differences are simply not that large. Moreover, the marginal popularity of a set of viewpoints among more intelligent individuals is not by itself a strong argument for their correctness. Some memes may be more appealing to intelligent people regardless of their validity, and memetic founder effects could easily cause ideas to be associated with certain populations.

A quick note on log odds

Probabilties are usually numbers that range from 0 to 1. However, the standard way of representing probabilities is not always optimal. However, there is another mapping of probability that goes from negative infinity to infinity. This system called "log odds" has a number of advantages. In the standard log odds approach, one maps the probability of an event x to the quantity log(x/(1-x)). Brian Lee and Jacob Sanders wrote a good summary (pdf) of this system which discusses its advantage and disadvantages. As they observe, use of log odds allows one to immediately see how something like the change in probability from 51% to 52% isn't that big whereas the change from 98% to 99% is a much larger change in the sense that the chance of the event not happening has now halved. Log odds helps makes this sort of intuition immediatelty obvious from the numbers. Brian and Jacob discuss the advantages and disadvantages of log odds in detail, and show how it is particularly useful for doing Bayesian updates. I strongly recommend reading their piece.

Occupy Wall Street, Boundaries, and Gratuitous Promotion of Family Members

My sister has a piece up at the Huffington Post discussing exactly how Occupy Wall Street lost her sympathy. She correctly points out actual problems with the Wall Street protesters, but I don't agree with what to her was the final point. She objects to the protesters deciding to protest the homes of the major executives, saying that they have a right to keep their private and public lives separate. I find this argument to be deeply unconvincing. When you are a major enough individual to be running a major corporation you have less of a right to privacy than a random individual. There might be an argument if these protests were directed at the homes of mid-level or upper level management. That argument doesn't apply to the CEOs of billion dollar corporations.

This is not a defense of the Occupy protesters in general. They aren't very coherent and those who have tried to state specific goals have given goals include goals that are unconsitutional, the immoral, the unethical, hopelessly naive, or just bad ideas. In that regard, they are essentially the left-wing equivalent of the Tea Party. It is possible that they will turn into something which does deal with the serious problems this country has, especially in regard to the massive income inequality which has become worse in the last few years but right now I'm not optimistic. The main thing that I would think needs to be done right now is getting the generic lower-middle class voter to understand that people like Herman Cain really have conflicting economic interests. There seems to be a certain class of economically badly off voters who somehow identify with the economic interests of people with incomes that are often an order of magnitude or more higher than their own.

As long as I'm pontificating about Occupy Wall Street, there are a few other things to note. First, whether or not one agrees with the protesters, the treatment of the protests by the police in some examples has been unacceptable. The mass arrest of protesters in Boston is a good example of this. Moreover, mistreating protesters is an easy way for people to build sympathy with a movement and come to agree with it whether or not the movement has any coherence or validity to their points. Second, using protesters behavior as evidence about economic policies is bad epistemology. This has lead to inane pieces like this one where various economic policies (some good, some bad) are justified simply by the existence of protesters. Protesters in this context are evidence of people unhappy with their current economic situation. Assuming that these people have any idea what to do about economic policy or that their existence can be easily traced to specific policies is unjustified.

In any event, my sister's piece is worth reading. She's not in the one percent, but she's not in the low percentages either. If OWS is going to succeed at anything they are going to need the people with average or moderately high incomes like my sister. Right now, they aren't doing that.

A brief note on non-transitive dice

I've talked before about non-transitive dice. We say that given a pair of dice X and Y, X beats Y if more than half the time when the pair is rolled X has a larger number face up than Y. It turns out one can construct dice A, B and C such that A beats B, B beats C, but C in fact beats A. This is a neat and weird property.

During a recent discussion I used non-transitive dice as an example of a counter-intuitive aspect of mathematics, I was pointed to an even weirder variant. Consider the following set of dice: A has sides (5,5,5,2,2,2), B has sides (4,4,4,4,4,1) and C has sides (6,3,3,3,3,3).

Here A beats B, B beats C and C beats A. But here's the really cool part: Let's say I roll two copies of A, two copies of B or two copies of C. Now things actually reverse! That is, a pair of Bs beats a pair of As and a pair of As beats a pair of Cs and a pair of Cs beats a pair of Bs.

This is a much more sensitive property than just non-transitive dice. Most sets of non-transitive dice will not have this property. We can also describe this sensitivity in a more rigorous fashion. Suppose we have a strictly increasing function f(x). That is, a function such that f(x) is greater than f(y) whenever x is greater than y. Now suppose we take a set of non-transitive dice and relable each value x with f(x). Then they will still be non-transitive. But, given a set of non-transitive, reversable dice, reversibility is not necessarily preserved by the f mapping. This reflects the much more sensitive nature of the reversible dice.

Here's a question I have so far been unable to answer: Is it possible to make a set of die which do an additional reversal? That is, is there a set of dices such rolling three copies the dice results in another reversal direction?

Voluntary Taxation and Gratuitous Promotion of Family Members

It looks like the last of my siblings has no entered the blogosphere. My sister Jacoba has a piece up at the Huffington Post discussing the reaction to Warren Buffet's statements that the rich are not being taxed enough. She points out that if people think that they aren't being taxed enough then they can always just right a check to the US Treasury.

Her point is an interesting one but I think it is misguided: Very few rich people think like Buffet does. Almost everyone who is in favor of higher taxes thinks that the group who should be paying higher taxes are the people with income slightly above their own income. Moreover, even if a large number of rich people agreed with Buffet, if those people gave much more of their money to the federal government while others in their income bracket did not those volunteers would suffer a relative loss of income. There's a fair bit of evidence that people's sense of status and wealth is a function of the people around them. So if most of the rich aren't paying as much it is quite understandable that the other rich would not want to. It is thus reasonable for some high income people to call for higher taxes even as they don't make voluntarily payments. In any event, the idea is an interesting one and the piece is worth reading.