User kcrisman - MathOverflow

Which rationals are sum-of-divisor function quotients

2011-04-15T17:44:43Z

Consider the function $\sigma(n)/n$, where $\sigma$ is the usual sum-of-divisors function. I read somewhere that it is unknown what rational numbers are in fact values of this function (or at any rate that characterizing them is an open question). Well, that was a while ago, and I suspect it was in one of my older references. So:

What is the current status of this question - characterizing the $q\in \mathbb{Q}$ such that there exists $n\in \mathbb{N}$ with $\sigma(n)/n=q$?

I think there is a standard name for the function $\sigma(n)/n$. If I knew it, that would make things easier, so I apologize if this is easy to find once one knows that.

Edit after accepting answer: Of course, $\sigma(n)/n=\sigma_{-1}(n)$, but I don't know whether there is so much more information under that designation!

Answer by kcrisman for Even Perfect numbers $n$ with $n+1$ prime

2011-04-24T02:38:46Z

The numbers involved are pretty huge - have you tried all the Mersenne primes' perfect numbers yet?

The other answer might be referring to Wagstaff's conjecture about the number of these primes being less than $e^{\gamma}/\log(2) *\log(\log(x))$; see e.g. here, here, or here for some references (some better than others).

I would imagine that this would be helpful in solving this, but gives a sense of just how hard it would be to prove anything.

Cyclic Permutations - but not what you think

2011-03-17T21:19:17Z

This question is not about elements of $S_n$ that consist of a single $n$-cycle, though naturally it's related.

Instead, consider permutations modulo the action of $(123\ldots n)$. That is, we want ABCD to be the same as BCDA and CDAB and DABC. (It's optional whether this also is the same as DCBA, but for now let's say it's not.) I am primarily interested in the graph that these generate, sort of like the Cayley graph for $S_n$ with generators $(12),(23),\ldots (n-1 n),(n1)$, but with vertices and edges identified. (I don't think this is a Cayley graph of a quotient of $S_n$; I don't even think this set is identifiable with a group since that subgroup isn't normal, if I recall correctly.)

What are these things called, and are there references to them in the literature? (Say to their symmetry groups, rep. theory, or whatever else.) I can't imagine there aren't, but because 'cyclic permutations' nearly always means something else, it's frustrating to look for this. I found pages of MathSciNet references to those terms, and none were about this. Not surprisingly! But presumably combinatorics experts have studied them - not just counted them, though Polya enumeration immediately comes to mind.

Edit: For a concrete example, imagine people around a dinner table, where you don't care which chair you sit in, you just care what the arrangement is. Maybe it's been thought of that way before?

Edit: Well, I have to say that Tilman and Mark Sapir both have been very helpful, but I guess Tilman answered the actual question.

Very oddly, I can only find ONE paper on MathSciNet that actually deals with the object I am interested in directly - Woodall's "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture" proves some basic facts. Nearly every reference to such things is about using cyclic orders without considering all of them (in graph theory or queueing theory), is using them to create ribbon graphs, or is about extending partial cyclic orders to complete cyclic orders.

Logical equivalences for FTA

2011-01-28T21:11:58Z

I hope this isn't a stupid question...

It's well known that (in the presence of various other axioms), Euclid's Postulate 5 ('parallel axiom') is equivalent to the Pythagorean Theorem. That is, assume Pyth. Thm. is true without Postulate 5, and you get the 'parallel axiom' as a theorem.

My question: Are there well-known (or not-so-well-known) theorems/properties of the ring of integers which are equivalent to the Fundamental Theorem of Arithmetic in this way? That is, things which are not just consequences of it, but imply it.

I have had a lot of trouble finding anything about this on the Net, but of course the words involved are not exactly unique! Please be gentle if there is something obvious I'm missing - I've put "elementary" as a tag by way of anticipating there is a clear answer. At least the statement is elementary!

Edit: I like all three answers for different reasons, and have voted up accordingly. None really answers my question, but that's because, upon further review, I think it's not well posed. After all, FTA is not an axiom like Postulate 5 (though of course one needs various axioms to prove it).

So maybe the answer about $a|bc$ is closest to what I was looking for, though as it happens I like to prove this first as well. Probably the best question would be how much one can prove in number theory without using the FTA. But that would be a different question! Thanks.

Answer by kcrisman for Consecutive numbers with n prime factors

2011-01-18T20:00:45Z

It would be interesting to know what generalization might be true about the starting numbers of such sequence, or at least the smallest such.

For instance, $P(7,2)$ and $P(8,2)$ are both true at 141 (and 212), so the smallest such number for only 7 is 323. The next smallest is 2302 (also for 7 only), and there are no others under a million.

Sorry for putting this in an 'answer'; it seems odd to me that one needs additional rep to put in a comment. Though I think that bounds on such numbers would be quite interesting.

Answer by kcrisman for Teaching undergraduate students to write proofs

2011-01-13T02:49:46Z

Let's say you choose 2. This is a sort of motivation-less course, naturally - all the things that will be proven, or at least many of them, are somewhat obvious to people who have lots of math experience, which the typical person to make it that far in the math curriculum will be (see David Bressoud's talks, of which that is one, for some fairly troubling statistics).

Okay, but you can turn that on its head. The reason such things are obvious (early in such a course, for instance, one usually proves that if $p|n^2$, then $p|n$) is because one has played with numbers a lot. So giving students something new in which to develop context and intuition is a great idea. Graph theory is a standard place to do this - proving easy things about colorings or connectivity - but one could introduce the groups $\mathbb{Z}_n$ or something with a little more structure than one initially thinks.

I saw a great talk where proving things about the decimal expansion of numbers was a big part of such a course. This can get into primitive roots, surds, etc., if you're ambitious - or just provide something a little off the beaten path.

Now, this doesn't look like an answer to your question, but it is. Namely, now that no one knows quite what the right answer is, the whole class can work together to make a proof that they all believe (and if they're wrong, you put it on the test). This isn't quite Moore method, but is of course influenced by it. Or you can make a journal for such things and give them feedback, or whatever you like. It's not the usual technique for teaching proof-writing, but is more realistic and can be easily complemented to the techniques you're currently studying (e.g., some graph theory stuff pretty much has to be proved by induction).

And something they've created from scratch is going to be much more effective in figuring out how to attack a proof. The key is that this will not be successful without doing it fairly consistently - not necessarily every day, but providing a consistent (perhaps weekly?) opportunity to do this.

Answer by kcrisman for Why does undergraduate discrete math require calculus?

2011-01-13T02:33:19Z

This has been dormant for a while, but it's worth pointing out the ACM recommendations, which essentially say what J W says - but I don't have enough rep to vote up that answer or comment on it, so I provide the link here for those searching for info. The ACM also recommended calculus in this set of recs, whereas the update is more about the core CS curriculum. It's also worth mentioning that the ACM is focused more on "sound reasoning", not "formal symbolic proof", in its guidelines. That doesn't necessarily mean less mathematical, from what I can tell.

Comment by kcrisman

2013-04-09T19:08:57Z

I agree that this particular proof is better than using Gauss' Lemma - similar in style, but less annoying - and gives a great chance to mention Eisenstein in a number theory class with no algebra prerequisites. I use it now myself, and relegate Gauss to an appendix.

Comment by kcrisman

2012-11-28T18:15:22Z

That said, there are other sites such as math.stackexchange.com where such questions would be welcome.

Comment by kcrisman

2012-10-17T02:52:05Z

Somewhat OT, hope it's ok - can you post a link to the "crazy example"? Sounds typical for non-Noetherian wackiness, would be good to have an easy reference, but my first few searches came up empty.

Comment by kcrisman

2012-02-09T03:58:53Z

Just FYI, this looks like a HW problem and not really too close to the guidelines - see mathoverflow.net/faq#whatnot.

Comment by kcrisman

2011-09-22T03:32:21Z

Yes, I think I found that site eventually at the time I was looking for this. Thanks.

Comment by kcrisman

2011-05-16T20:41:55Z

So, two prodigy lives before math. Not sure this counts :)

Comment by kcrisman

2011-04-15T18:37:01Z

'Abundancy Index' - got it. Thank you!

Comment by kcrisman

2011-03-18T13:20:24Z

Ah, but I care about the automorphism group of the graph of such things. So I still get representations :) Thanks!

Comment by kcrisman

2011-03-18T00:31:58Z

Hmm, that is helpful. Is there any information out there about this particular Schreier graph? It would surprise me if these cycles hadn't been discussed somewhere.

Comment by kcrisman

2011-01-19T13:25:46Z

I verified @Aaron Meyerowitz about the run of 9 by brute force up to 125 million as well. Nice work.

Comment by kcrisman

2011-01-18T21:46:38Z

Not being able to comment on other answers is really annoying... Anyway, the Forbes paper is about $\Omega(n)$, but here the question is about $\nu(n)$, the number of distinct prime divisors (see, for instance, Shapiro's NT text for this notation). So it's relevant, but not about the same question. From that paper: "The smallest example with m = 2 is {33,34,35}" - but of course that is not the maximum length with the OPs question, since the naive upper bound of $2^m-1$ (in the paper's notation) is no longer relevant.

Comment by kcrisman

2011-01-13T15:44:12Z

Well, of course it depends on the clientele, as it were. And I wasn't recommending basing the whole course on graph theory - that is the OP's option 1. I'm just suggesting a possible supplement to a type 2 course. With respect to your friend's experience, I've had the opposite reaction - students who never really cared about why it was useful; they just loved drawing the graphs! I suppose there are as many experiences as groups of students.