User gerhard paseman - MathOverflow

Erik Westzynthius's cool upper bound argument: update?

2010-09-04T01:41:49Z

In a paper of Erik Westzynthius,

Ueber die Verteilung der Zahlen, die zu den n ersten Primzahlen teilerfremd sind, Comm. Phys. Math. Soc. Sci. Fenn., Helsingfors (5) 25 (1931), 1-37

I saw the following upper bound argument. Having never studied sieve theory, I was quite impressed by it. The goal is to bound from above the quantity max $(q_{i+1} - q_i)$, where the $q_i$ are the positive integers in increasing order which are relatively prime to $P_n$, the product of the first n primes. Here is a sketch of the argument.

Let $a$ and $x$ be real parameters, with $x > 0$ . Consider the integers in the open interval $(a, a+x)$, and call this set $H$. Let us look at the subsets of $H$ consisting of those integers which are a multiple of the positive integer $t$; call the size of each such subset $I_t$. Step 1 is to use inclusion-exclusion to estimate $I_0$, the number of integers in the interval $(a, a+x)$ which are relatively prime to $P_n$. (I.e. count integers, throw out multiples of 2, throw out multiples of 3, add in multiples of (2*3) to compensate, etc.) We get

$I_0 = \sum_{t \in R} [I_t * (-1)^{\mu(t)}] $.

Here $R$ is the set of positive integers which are of the form (warning: sloppy notation) $\prod_{J \subset n} p_j$, that is all integers whose prime factorizations have only primes less than or equal to the nth prime, and those occuring only to at most the first power. (More succinctly, $R$ is also the set of positive divisors of $P_n$.) For such a number $t \in R$, $\mu(t)$ is precisely the number of prime factors in $t$, and $\mu$ is chosen to suggest the Moebius function whose value at such $t$ is $(-1)^{\mu(t)}$. The equality is exact.

Step 2 is to replace $I_t$ with a linearized approximation plus an error term which I will call $E(t)$. This substitution gives:

$I_0 = \sum_{t \in R} [ (E(t) + x/t) * (-1)^{\mu(t)} ]$ .

Since the number of multiples of $t$ in the interval $(a, a + x)$ is roughly $x/t$, the error term $E(t)$ is bounded in absolute value by $1$. Step 3 will rewrite the RHS and estimate it pessimistically: $E(t) * (-1)^{\mu(t)}$ will be replaced by $-1$, and the alternating sum of $x/t$ terms can be rewritten as a product involving terms of the form $(1 - 1/p_i)$, where $p_i$ is the $i$th prime. There are $2^n$ terms of the form $E(t)$, so one gets:

$I_0 \geq [x * \prod_{1 <= i <= n} (1 - 1/p_i) ] - 2^n = x/Q - 2^n$ .

Here $Q$ is an abbreviation for $1$ divided by the product of the n terms $(1 - 1/p_i)$. It is roughly log(log(n)) for large n. Here comes the kicker. Step 4 notes that steps 1 through 3 are essentially independent of $a$, and if $x$ can be chosen so that $x/Q - 2^n > 0$, then $I_0 > 0$ which means at least one of the $q_i$ is in the interval $(a, a+x)$ when $a > 0$, and such $x$ would be an upper bound for $q_{i+1} - q_i$ which is independent of $i$. So choose $x = Q * 2^n$ plus epsilon.

I thought it a neat enough argument (especially the kicker) that I am sharing it here with other non-students of sieve theory. Now to the questions.

1) Is there any work done which improves the upper bound for $q_{i+1} - q_i$? The answer to this is yes, since in a footnote Westzynthius shows how to improve the bound to $Q * 2^{n-1}$ by counting odd multiples. So I really want to know if there are even better bounds out there, done by additional researchers. I would expect a provable bound to be $Q * 2^g$, where $g$ is something like a polynomial in log(n), but even having $g$ be n to a fractional power would be something.

2) Is there work done which uses something like the Bonferroni inequalities to improve the above argument?

3) Did Westzynthius publish any other work (possibly nonmathematical) besides the paper that includes the argument above?

Motivation: I am considering improvements to this argument which do establish better upper bounds, and am wondering how to push the exponent from n - o(1) down to poly(log(n)). Especially, I want to know if I am rediscovering how to replace n by cn for some $c < 1$, as opposed to discovering how to do it.

Gerhard "Ask Me About System Design" Paseman, 2010.09.03

Better error bounds for partial sums of reciprocals of primes?

2012-07-20T06:44:35Z

One of Mertens' theorems gives that

$$\sum_{ p \text{ prime,} p \leq k } 1/p - \log{\log{k}} = B + E(k)$$

where $B$ is a constant near $0.26$ in value and $E(k)$ is an error term whose size is dominated by something close to $4/\log{k}$, when $k$ is large enough to make the sum meaningful.

I want to work with partial sums of the above with $j \lt p \leq k$, so that I can say the partial sum of the reciprocals of primes greater than $j$ and at most $k$ is $\log{(\log{k}/\log{j})} + E(j,k)$ where $j$ is not too small (perhaps $j \gt 3$ or $5$), $k$ not too large, say $j^\alpha \lt k \lt j^\beta$ where often $1 \lt \alpha \lt \beta \lt e$, and $E(j,k)$ is comfortably small. Unfortunately $4[1/\log{k} + 1/\log{j}]$ looks too big for me; I am hoping to have (for large enough $j$) $E(j,k)$ bounded by something that is $O(1/j)$ or better.

I have access to Mark Villarino's treatment of Mertens' theorem. As of 2005, it seems $E(k)$ is no better than $O(1/\log{k}^2)$ I also hope to obtain recent work of Pintz and Diamond on oscillations ia related formula which is Mertens product formula, but I do not see yet how it will me help me with this formula.

As I am still a tyro at number theory, I don't even know how realistic my hopes are for $E(j,k)$ to be $O(1/j)$. Can someone who is familiar with the recent literature give me a guide post? Either references or heuristics showing what sort of bounds to expect for $E(j,k)$ or even $E(k)$ would be welcome.

UPDATE 2012.07.24 I want to acknowledge the contributions of joro, Christian Elsholtz, and Eric Naslund. joro and Eric helped me realize that expecting $O(x^{-1/2})$ error even conditionally is expecting a bit much, and Christian helped me realize that Dusart still has some nice unconditional refinements. I will likely accept Christian's answer, but not before I do some computations of my own. In particular, Rosser and Schoenfeld have in Theorem 20 of their 1962 paper on functions relating to primes a nice difference of $2/(x^{1/2}\log x)$ which is valid for $1 \lt x \lt 10^8$ between lower and upper estimates for the sum of interest, and I may end up using or refining that estimate in combination with Dusart's results for larger $x$ for my own nefarious purposes. I am hoping in particular that the oscillations will be slow enough that my desired partial sums from $j$ to $j^\alpha$ will have very small error. END UPDATE 2012.07.24

Gerhard "Ask Me About System Design" Paseman, 2012.07.19

Answer by Gerhard Paseman for Can you randomly sample graphs with quadratic growth?

2011-12-02T19:28:54Z

As (up to isomorphism, and changing font) $G_0$ has 1 member and $G_1$ has 4, I leave it to the poster how to implement random selections from these classes. That should be straightforward.

I am about to turn enumerating $G_2$ over to a computer, after spending hours trying it by hand.

My chief challenge in attempting the enumeration was to wire up the 8 distance two neighbors to each other in a way that the results could be extended to a member of $G_3$. If I ignore that I have (not an exact number) on the order of 50 nonisomorphic candidates each of which could produce potentially thousands (more specifically, O(28 choose 6)) of members of $G_2$.

Something that may work efficiently by computer for which I have trouble attempting by hand is stitching: there are 4 nonisomorphic members of $G_1$, and you can try stitching such members together in all possible ways to form larger subgraphs of members of $G_2$ or $G_3$. Be sure to check that you don't put in too many distance k neighbors when doing so.

If it turns out that stitching yields a small number (less than a thousand) of members of $G_2$, then it may be computationally feasible to enumerate $G_3$. Until I see an enumeration of $G_2$, any further guesses I make on this are essentially wild speculation.

Gerhard "Real Hand-stitching Is Even Harder" Paseman, 2011.12.02

Answer by Gerhard Paseman for Number of spanning trees which contain a given edge

2011-11-18T21:10:55Z

The assertion below regarding O(1/n) is in contradiction with another posted answer, so I leave the construction available while I check the assertion.

Let M_n be the (graph of the Hasse diagram of the) modular lattice on (n+2) elements. This will have 2n edges. Add two more edges on either side. Call the leaves u and v, and let us add an edge (the problem edge, called e) between u and v. I have a u-v gadget with 2n+3 edges on n+4 vertices, and n-many cycles of length 5. However, u and v have degree 2.

Now to the u side of this gadget, add an edge and then dangle whatever favorite nonempty graph off this edge, and choose a disjoint graph to dangle off of v. In this graph, u and v have degree 3. However, any spanning tree that contains e can be modified to one of at least some number of other spanning trees; the analysis is more complicated than I originally imagined, but I think one can use this to show the ratio for this edge is at most O(1/n). So if d and d' are at least 3, I see no useful lower bound for the fraction in terms of the degrees themselves regarding edge e.

Gerhard "Ask Me About System Design" Paseman, 2011.11.18

Answer by Gerhard Paseman for Covering $\mathbb{N}$ with prime arithmetic progressions

2011-11-18T16:48:45Z

I like Aaron Meyerowitz's efforts and think his and similar methods deserve further study. I want to post my skepticism as a counter, and hope that something will arise from the contrast. I do not consider this post as being an acceptable answer though.

The problem is essentially a shifted sieving problem. After taking the first $n$-many (finitely) primes $q_i$ with offsets $r_i$, one has an eventually periodic pattern of uncovered integers which repeats with period $Q_n = \prod_{i \leq n} q_i$, which contains $U_n = \prod_{i \leq n} (q_i - 1)$ uncovered numbers in each period, and has the first period starting somewhere near $M_n = \max_{i \leq n} r_i$.

If the $q_i$ are the primes in ascending order, we have (Mertens) that $U_n$ is $O(Q_n/\log(q_n))$, which is (roughly) about $n$ times as many primes in the interval $(M, M + Q_n)$ when $n$ gets large, especially when $n$ is comparable to the largest integer $M$ allowed to be uncovered.

If the distribution of coprimes to $Q_n$ were amenable to being nicely covered by arithmetic progressions of primes less than $q_n$, I might share Aaron's confidence. However, each later prime $q$ used is itself coprime to $Q_n$, and with small deviation will cover only about $1/q$ of what needs to be covered. I suspect that when $n$ gets to be about $Q_{24}/2$ using Aaron's sequence $Q_i$, he will run short on primes. It might be prudent to try more extensive simulations which leave no numbers greater than 50 uncovered.

Gerhard "Saying As I Feel It" Paseman, 2011.11.18

Answer by Gerhard Paseman for Sum of combinations

2011-10-28T20:22:20Z

If you are interested in approximations to your ratios, you may find the accepted answer (and some comments of mine) to this MathOverflow post useful: http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n .

Essentially, the approximations are geometric series starting with the dominant term in your sums, and except for k near n/2, should serve you well, especially if you collapse adjacent terms in the form of n^2 +1 choose j. For k near n/2, Michael Lugo has some suggestions in his answer to the question above. If you do a search on "binomial coefficients sum", you will find other MathOverflow posts considering sums similar to yours which might help you.

I think getting a nice closed form for the exact values for your numerators in general is unsolvable.

Gerhard "Ask Me About System Design" Paseman, 2011.10.28

What is due diligence when translating a paper?

2011-10-27T05:43:48Z

EDIT: Part of the community has decided on a less catchy and more representative title than "Socially acceptable plagiarism (with regards to translation)". Let's run with that for a while. GRP.10.27 END EDIT.

The catchy part of the title refers to reusing words or ideas without permission, but without 'rocking the boat'. In mathematics, this is often done by proper attribution of the source, by naming the author/speaker, or providing other clues that the phrasing one has just used is not original.

If this were a discussion forum, I would invite answers that lists various forms of socially acceptable plagiarism; instead I prefer brief mention of such to the comments. This post is about the propriety and etiquette involving translations.

My situation is that I want to devote time to producing an English translation of some papers in German, and make the results available. Assume (although I may end up doing something different) that I place my efforts in a PDF and put it on some web page for public Internet access.

Primary question: What trouble do I get into by doing that?

Answers to this may depend on what things I did wrong, especially if I use certain words, phrases, images, parts of images, without crediting the source or asking for permission. So let's add to the context that the papers are from before 1980, the authors are likely unresponsive, and the source journals are likely discontinued, although online access to the sources are not freely available. I will list the original sources in the PDF, but the following question arises:

What trouble may happen if I do not contact some representative and ask for permission to use old material?

For material published in 1980 and afterwards, there is less of an excuse not to seek such permission or rights, and I would accept anecdotes that might lend guidance and are not obvious applications of common sense, but I am interested in the amount of effort someone in academics expends in order to reuse published material, especially in translated form. I know of a few examples in book publishing where more effort is made in getting such permission, however that appears more expensive than I feel the current scenario merits. This leads to:

What is "due diligence" in producing such a translation? Does it matter if the translation is provided gratis or for a fee?

I don't expect to sell access to the translation; it is my intent to make it freely available to any individual researcher. If someone else wants to put it in a book and sell that book, however, perhaps I could grant them such rights in exchange for a small monetary (or caffeine-ary) consideration.

Finally, let's assume I provide my own translation, except that for some small sections (possibly in a different language) I use someone else's translation of the same or related source. Let's say that I am concerned especially about a fragment that is (roughly) three paragraphs or about 200 words long. The answer to the following questions may be length dependent: if so, consider that I also have a 20 word fragment that is of concern.

How do I attribute this fragment? Do I use a footnote, or mention it in a preface? What is due diligence for making sure I can use this fragment?

This question is barely suitable for MathOverflow; I ask it here because the papers and output are mathematical, and the conventions in mathematics and mathematical publishing may not be addressed were I to ask these questions elsewhere. If they are addressed elsewhere, please provide a pointer to such material.

Also of interest, although I do not need the answers here, is if I have the same situation as above, except that I provide an interpretation (which is laced with my own perspective) rather than a translation (which attempts semantic fidelity and objectivity with respect to the source paper). The answers may stay the same, but it feels like a different situation to me. (A similar situation is mentioned in http://mathoverflow.net/questions/73463/ , which has some useful advice, although it does not involve natural language translation.)

Gerhard "Yes, It's About Jacobsthal's Function" Paseman, 2011.10.26

Answer by Gerhard Paseman for What is due diligence when translating a paper?

2011-10-28T17:17:47Z

I want to acknowledge the contributions others have made; I choose the answer format to help with emphasis.

I should have mentioned copyright issues in the question, as that is the major consideration when asking about trouble; thanks to Michael Greinecker for pointing this out and to Henry Cohn for expanding upon this. (This teaches me to preview questions on meta.mathoverflow where being, shall we say, less thoughtful carries less stigma or less embarrassment.) Since this handles the primary question, I will accept one of their answers if a) they submit an answer with that content and b) no one else gives a more thorough answer regarding due diligence.

Much as I liked my original title, I thank darij grinberg for changing it to reflect a key issue of the series of questions. (I do have mixed feelings, grumble, grumble. At least I read the bit in the FAQ about collaborative editing before posting.) Although I am still interested in hearing of other examples of socially acceptable plagiarism, I agree with darij that this question is more about due diligence with respect to translations.

I am glad for Gerald Edgar's contribution; I am hoping to see more anecdotes like those, and I should have said so more loudly. I will wait at least three days and then accept his answer if I do not see one I like even better.

I also thank David Speyer and KConrad for their remarks. I have not yet decided, but their comments sway me towards writing an expository article which contains my intepretation of the papers of interest, and adds some original material. That would force me to do more summaries and cutting, but that may be a good thing.

Based on the number of views and votes, and the fact that the question is still open, I thank the community for tolerating this kind of question. I hope more good answers will appear so that this can serve future readers.

Gerhard "Can't Wait For Oscar Night" Paseman, 2011.10.28

Answer by Gerhard Paseman for biggest cube problem (given set of bricks)

2011-10-16T05:01:56Z

In general the problem should be NP-hard. While this may not be a reduction, I am thinking of trying to pack n^2 many 1 by 1 by n bins with 1 by 1 by k bricks, where k actually means many bricks of different sizes; if I am right, bin packing can be reduced to your problem.

If the bricks are of few types, it may be possible to construct quickly tiling solutions that allow one to get nice approximations. For example, 3 of the 7 blocks used to build a Soma cube each tile the 2x2x2 cube, so given any count of those 3 kinds of blocks, you can likely come within O(1) of the maximal cubical volume achievable using little more than arithmetic; if you can generate dissections of small cubes or prisms with your input bricks, you can then quickly decide which of many rectangular prisms are nicely buildable with the given tile set, and this can be used to approximate the maximal rectangular volume, or maximal cubical volume, as desired. Note that this does not contradict the above (idea for a) reduction because k in this instance is bounded from above by some small number.

Gerhard "Ask Me About System Design" Paseman, 2011.10.15

Answer by Gerhard Paseman for About the asymptotics of LCM

2011-10-13T19:06:25Z

There are some basic results about LCM that you can use. Here's one: for any increasing sequence of positive integers $a_1 \lt \ldots \lt a_n$, one has $a_n \leq LCM(a_1 , \ldots, a_n) \leq a_1 \times \ldots \times a_n$ . So if $a_n$ increases quickly enough, the difference between the logs of the upper and lower bounds will be small compared to the log of the LCM, so the logarithm of the logarithm of the LCM may have a computable limit.

There may be a statistical difference between using $x$ and using $g(x,c)$, but I am having a hard time seeing it for general $x$. Letting $b_n = LCM(a_1, \ldots, a_n), a_{n+1}$ will have to be pretty special in order for $b_n$ not to be coprime to any number between $a_n$ and $a_n + c$ inclusive even when c is smaller than $\log(b_n)$; even then, most such numbers will have a small factor in common with $b_n$, so you might as well replace $g(a_{n+1},c)$ by a number coprime to $b_n$ that looks like a small multiple or factor of $a_{n+1}/log(b_n)$.

Given that the limiting probability of two positive integers being coprime is $6/\pi^2$, I would suspect that $b_n$ will "look like" a small multiple of the product of perhaps 2/3 of the members of the increasing sequence in the case that the increase in a_n is exponential or near exponential. If your sequence increases slowly, the LCM will most likely increase in a fashion similar to the factorial or primorial function.

If you provide some motivation, I may be able to give some definite answers toward the motivating problem.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2011.10.13

Answer by Gerhard Paseman for Optic fibers after Joseph O'Rourke

2011-10-13T18:04:50Z

This is a suggestion rather than an answer. I've decided to think out loud in the hopes that someone else can take the thinking and run with it.

Consider the picture from the ray's point of view, and let's consider a (possibly not more restrictive) definition of a "good optic fiber", which I will not give but only suggest here. A good optic fiber makes sure that not only can light pass through both ways (i.e. is bidirectional) but doesn't slow down much. I originally thought of the 2 dimensional version of this as "For every point p, make sure reflected light off p goes further down the tube in the same direction", but now I am thinking "for every open patch on the tube whose reflection through p does not intersect with itself, make sure that reflection does not change much." So the idea is the light coming from a part of the wall of the tube (P) hits p, and reflects to hit another part of the tube (Q), that P and Q are disjoint and satisfy some conditions if they are sufficiently small, say if P has area at most epsilon then Q is guaranteed to have area not much different from epsilon times the appropriate linear scaling.

With an appropriate definition of "good optic fiber", you may be able to show that light travels quickly through the tube as long as the entrance ray is less than, oh say 89.9 degrees off the perpendicular axis of the tube. The next thing would be to show that any optic fiber can be epsilon-approximated by good optic fibers (or not), and then if our luck held, show that the answer to both questions would be NO for good optic fibers and that the answers would hold in the limit of the approximations.

Stop me if you heard this one before.

Gerhard "Oh Wait, I'm Done Already" Paseman, 2011.10.13

ASCII prime plots and prime-rich quadratic polynomials

2011-10-11T07:15:59Z

This is a series of questions inspired by the MathOverflow question http://mathoverflow.net/questions/77141/find-the-least-prime-so-that-p-1-has-two-factors-greater-than-m-and-n posted by Aaron Sterling.

I suggested plotting primes by marking the status of the number $(nm+1)$ at coordinate $(n,m)$. Using commutativity, I have combined two ASCII art plots for $1 \leq n,m \leq 50$ in a figure-ground contrast. (Perhaps Joseph O'Rourke will be inspired to provide some similar but nicer looking plots for other ranges of $n$ and $m$.) In the plots below, + indicates $nm+1$ is prime, and other characters (after a shift in one coordinate) indicates whether $nm + 1$ has a factor of two, three or five.

+  .o.Oo .oO o .O. o Oo. oO.o. O .o.Oo .oO o .O. o Oo
++  O o  O  o Oo  oO o  O  o Oo  oO o  O  o Oo  oO o
 +   O . .O. . O . .O. . O . .O. . O . .O. . O . .O.
+ ++   oO o  O  o Oo  oO o  O  o Oo  oO o  O  o Oo  o
 +     . o .o. o .o. o .o. o .o. o .o. o .o. o .o. o
+++ ++     O    O    O    O    O    O    O    O    O
   + +   Oo. oO.o. O .o.Oo .oO o .O. o Oo. oO.o. O .o
 +  +     O o  O  o Oo  oO o  O  o Oo  oO o  O  o Oo
 + +   +   . O . .O. . O . .O. . O . .O. . O . .O. .
+ ++ ++  +   o  o  o  o  o  o  o  o  o  o  o  o  o  o
 +   + +     . oO.o. O .o.Oo .oO o .O. o Oo. oO.o. O
+ + ++ ++     O    O    O    O    O    O    O    O
   + +   + +   Oo. oO.o. O .o.Oo .oO o .O. o Oo. oO.o
 ++ +  ++    +    O  o Oo  oO o  O  o Oo  oO o  O  o
 + +     + + +   . . . . . . . . . . . . . . . . . .
+    ++    +  ++   o Oo  oO o  O  o Oo  oO o  O  o Oo
     + +     +     O o .O. o Oo. oO.o. O .o.Oo .oO o
++ + ++ +++   + +   O    O    O    O    O    O    O
         + +         .oO o .O. o Oo. oO.o. O .o.Oo .o
 ++ +   +  + +     +    o  o  o  o  o  o  o  o  o  o
 +   +   +     + + +   . .O. . O . .O. . O . .O. . O
+ ++    +     ++ ++ +   Oo  oO o  O  o Oo  oO o  O  o
 +   +     +       +     O o .O. o Oo. oO.o. O .o.Oo
  ++   + +  ++  +++    +    O    O    O    O    O
   + +   +     +       +   .o. o .o. o .o. o .o. o .o
 ++ ++     +    +  ++ +  +    oO o  O  o Oo  oO o  O
   + +   +   + + + +         O . .O. . O . .O. . O .
+  +  +  + +  ++     + ++ +   Oo  oO o  O  o Oo  oO o
 +     +   +     +             . O .o.Oo .oO o .O. o
++  +++++ +  +   ++++++ + +
         + +         +           .o.Oo .oO o .O. o Oo
  +  + +  +  +   + ++  +    +     O o  O  o Oo  oO o
 +   +   + + +     + +   +   +     O . .O. . O . .O.
  ++  + +  ++    ++       ++ +  +    oO o  O  o Oo  o
 +   + +   + +   + +     +   +       . o .o. o .o. o
+++ +     ++  +++   + +  + +  ++   +     O    O    O
   + +         +                 +     Oo. oO.o. O .o
    ++    ++  + +  +        +  +        O o  O  o Oo
 + +   +     +       + +   + + + +   +   . O . .O. .
+    ++  +  + ++  +  +       +  ++  +  +   o  o  o  o
 +               + +         +       +     . oO.o. O
+ + +  ++++ + ++ +  + ++++    +  ++  +  +   O    O
   +     +           + +     +     +   +     Oo. oO.o
 +     ++    ++    +  +     ++ ++               O  o
   + +     + +   +   +   +       + +   +       . . .
+ +  +   +  + +  +  ++  +  + ++    +     ++      o Oo
     +       +     +   + +         + +     +     O o
 + ++ + +  + + +    +  ++++   +     + +  + ++     O
   +     +       +         + +   +                 .o
 ++ +  +   + ++     + ++ +  +  +   + ++     + +

Based on this plot, I suspect my conjecture about the prime "nearest" to and greater than $n*m$ being at most $4nm$ not only holds (as a sort of 2-dimensional Bertrand's conjecture), but that this prime differs in taxicab distance by $O(\log(nm)^2)$. In other words, there is an absolute constant $C$ such that there is a prime $p$ with $p-1 = n'm'$, and with $n \leq n' \leq n + C\log(nm)^2$ and also $m \leq m' \leq m + C\log(nm)^2$. I am interested in information supporting or refuting my suspicion (and I suspect Aaron Sterling shares this interest), but that is incidental to what follows.

The primary question is a reference request: has anyone seen a plot like this before in the literature? I know of Ulam Spirals ( http://en.wikipedia.org/wiki/Ulam_spiral ) and it seems that artefacts in the plot might be related to a conjecture of Hardy and Littlewood regarding primes of the form $ax^2 +bx +c$. What I find striking are the diagonals that occur in the plot, especially those starting at $(a,a)$ and continuing in the direction $(2,-1)$. In particular, the sequence 101,109,113,113,109,101,89,73,53,29 appears as such a diagonal. Is it possible that primes of the form $a^2 + 1$ lead to prime rich polynomials of the form $(a+2t)(a-t)+1$? The secondary question series is: what is known about prime rich quadratic polynomials, and does such knowledge follow naturally from studying plots like those above?

Gerhard "Ask Me About System Design" Paseman, 2011.10.11

Answer by Gerhard Paseman for Factoring some integer in the given interval

2011-08-04T17:47:40Z

I think Felipe Voloch has the right sense about the problem: you should expect to encounter a prime or a number which is a small number times a prime. Since you suggested probabilistic and did not mention that you wanted ONLY the desired number output, here is a start on your desired program.

Pick a desired small bound B, which will be the largest of the primes to be sieved out. Make B compatible with the desired running time of your eventual program, but I like Felipe's suggestion of $O(\text{log}^2N)$. Now for each prime $p$ up to B, compute the remainder of $N$ after dividing by the largest power of $p$ that is smaller than $N$. Use this to populate an array of length of your interval with powers of $p$ which are the factors of the corresponding numbers. This should take (B/log(B)) times $O(\text{log}N)$ time and space.

At this point you have several options. The simplest one is to perform the divisions and list out the cofactors as well as the small factors. Even with B smaller than Felipe's suggestion, you will most likely have printed out the complete factorization of one of the numbers. Use whatever time you have remaining to find it, either by doing quick primality tests on all the candidates or slow primality test on some appropriate subset. An alternative is to continue eliminating small factors, for once $p$ is larger than your $O(\text{log}N)$, you won't need to worry about picking powers, but can switch to doing gcd with 0 or 1 numbers in the interval.

In short, there is a way to make an efficient version which is morally equivalent to trial division, and still have time left over to pick with high chance of success the completely factored number.

EDIT 2011.08.10 I got curious, so I asked a question and did some computations with B=2, with the expectation that I would find very few intervals of the form $[N - \text{log}_2N ,N]$ which did not contain a prime or a power of 2 times a prime, or a power of 2. The data so far are contrary to my expectations: if I haven't messed up the programming, there are more than 200 such $N$ less than $10^5$. Although I still think the small intervals will contain a B-smooth number for B not too large, this recent data puts a measure of doubt in my mind. END EDIT 2011.08.10

Gerhard "Ask Me About System Design" Paseman, 2011.08.04

How small can intervals be and still contain a prime times a power of 2?

2011-08-10T22:50:01Z

There was a question on MathOverflow which has since disappeared, that was on sums of at most M B-smooth numbers. It asked several questions related to how many could be found in the interval $[N-d,N]$, where $N$ was given and $d$ was some parameter of size to be determined, but a starting guess for $d$ was $O(\text{log}N)$. I can't refer to it, but I can refer to another question on factoring some number in an interval, namely this question.

These questions, and other questions, and my thinking about Jacobsthal function, lead me to present the following. Recall a positive integer $N$ is B-smooth if every prime factor which divides $N$ is less than B, or $N$ is B-smooth and $p \mid N$ implies $p <=$ B . Let me call $M$ B-factored (there may be standard terminology but I do not recall it) if $M=PN$, where $N$ is B-smooth and $P$ is either 1 or $P$ is a prime larger than B.

I suggested that for B not large there were likely to be occurrences of B-factored numbers in an interval of the form $[N-d,N]$ as above, and that if a probabilistic algorithm to find one was wanted, a simple one could be devised using trial factorization, Fermat tests, and other handy ingredients. Also, if $d$ were $O(\text{log}N)$, the chances of success at finding one (and then later verifying the complete factorization using some computationally expensive test) were very high.

I am now convincing myself that the probability of success is in fact 1, and this would jar (but not necessarily contradict) with the intuition I am developing about gaps between primes. So I ask for help with some questions to create some clarity.

In the following, B=2, and I will ask the reader to create her or his own variation with larger B. Also let $d = \text{ceil}(\text{log}_2(N))$ until we change it (so for most $N$, $d$ is the number of bits used in writing $N$ in binary. First a (hopefully true) result.

1) For $N > 2$ there are $\pi(N)$ B-factorable numbers in the interval $(N/2,N]$ .

This result suggests (but does not imply) there are at least twice as many B-factored numbers as primes in $[N-d,N]$.

2) True or false: for $N > 1$, there is at least one B-factored number in the interval $[N -d, N]$ .

This should be true be considering how thin the complement of B-factored numbers is intially; even though they grow to an eventual density of 1, I imagine (but do not know) that they do so slowly enough for 2) to be true.

3) How small are the gaps between B-factored numbers? In other words, how much can $d$ (as a function of $N$) can be adjusted so as to be made true?

Even though there are gaps between primes which are several times larger than the average gap d, it is suspected such gaps get no larger than $O(d^2)$, and observed gaps are much smaller. I am working with the idea that such gaps get no larger than something like $cd(\text{log} d)^3$ for some small constant $c < 4$. For B-factored numbers, a large gap between them is like asking for $\text{log}_2N$-many large gaps to appear in the primes at just the right places, and so that one can expect or even prove reults much better than 2) above. Also, one can ask for $d$ as a function of B and $N$, but I prefer the simple version with B=2 for now

EDIT 2011.08.10 A computer run suggests that there are no 2-factored numbers in the interval $[2312,2325]$. This is the smallest of many such examples saying that 2) is false; my computer also says 35647 is the last of 30 consecutive numbers which are not 2-factored. It may be that Greg Martin is right and that some proofs in the literature can be expanded to include this case. However, there is still B$>2$ to be considered. END EDIT 2011.08.10

Gerhard "Ask Me About System Design" Paseman, 2011.08.10

How many sequences of rational squares are there, all of whose differences are also rational squares?

2011-08-03T21:17:10Z

After commenting on a question of Joseph O'Rourke's, I thought it interesting that a number theory result (artihmetic progressions of rational squares cannot be arbitrarily long) had applications to geometry (don't look at mostly regular cones of regular hypercubes for totally rational polytopes). (I hope I got the above right and that it is indeed an application; I proceed on that basis.) Of course I am also impressed by the fact that there is no known geometric proof of the fact that finite geometries satisfy both or neither of the configurations of Pappus and of Desargues. So of course, a natural question would be to consider applications of number theory to geometry; I'm not going to do that here. Instead, I will ask for assistance with Joseph's program by asking a question about rational squares.

The first question that occurred to me was " (1) Is there a sequence of integer squares whose differences are also integral squares?" For sake of interest I require all squares to be nonzero, though later they may be rational and not just integral.

Before posting this question, I saw the answer was yes, and that indeed there were at least countably many such sequences, although I don't know if there are infinitely many tails. So I nominate question first':

(1') How many infinite sequences of integer squares are there, all of whose first differences are also integer squares?

There is the potential to be uncountably many such, especially if there are (is?) an uncountable infinity of tails. But wait! There's more!

(2) Fix an integer $k$ with $k > 1$. How many infinite sequences of integer squares are there, all of whose first through $k$th differences are also integer squares?

Recall that for a sequence $a_i$, the first difference is the sequence $b_i = a_{i+1} - a_i$, and the $(k+1)$st difference is the first difference of the $k$th difference. I suspect that for $k$ large enough, the answer will be zero. However, those are just warm ups for this question:

(3) How many sequences of rational squares are there such that for every positive integer $k$ all $k$th differences are also rational squares?

Motivation: I think it is a cool set of questions. Also I think that if Joseph is going to get a family of rational polytopes of arbitrarily high dimension, he will find such sequences useful (I am thinking volume of a pyramid being base times height times some rational number in combination with a multidimensional Pythagorean-type expression), and that such a family will imply the existence of such sequences, but I do not see the converse as the polytopes have to satisfy additional relations. As usual, reference requests and related problems are welcome.

Gerhard "Ask Me About System Design" Paseman, 2011.08.03

Answer by Gerhard Paseman for Is the following DNN matrix CP?

2011-07-29T01:50:48Z

Edit: I wanted the following matrix to be $W$. Robert Israel suggested I call it $W^T$ instead. I defer to his years of experience and the fact that it gives a better answer to the problem. End Edit.

For 6 times the given matrix, I nominate the following candidate for $W^T$

$$\begin{bmatrix} 1 & & & & 1 & & & & 1 \\ 1 & & & & & 1 & & 1 & \\ & 1 & & 1 & & & & & 1 \\ & 1 & & & & 1 & 1 & & \\ & & 1 & 1 & & & & 1 & \\ & & 1 & & 1 & & 1 & &
\end{bmatrix} $$

Does this help?

Gerhard "Ask Me About Binary Matrices" Paseman, 2011.07.28

Answer by Gerhard Paseman for Cubic graphs which are "difficult to navigate"

2011-07-28T04:27:05Z

Since you used the word "travelled", I am guessing you want a traversal-based type of algorithm. If you have other means of searching the graph, you should make it clear.

This really sounds to me like a cow-path problem. However, you might try search games to see if other algorithms like those for the Chinese postman problem are more suitable for your problem. If you do a web search on cow-path, you will find a randomized algorithm where the expected runtime is (a real number which is) about 7 times the distance from the goal.

Gerhard "Ask Me About System Design" Paseman, 2011.07.27

Answer by Gerhard Paseman for Counting restricted polyominoes

2011-07-23T06:10:23Z

EDIT 2011.07.26 This post is too long already. In brief, the choices made for staircases, modified staircases, and variations means that for most animals, exactly one rotation or reflection produces a different animal. The exceptions are crosses, of which there are $O(n^3)$, and "symmetric" animals, which are in 2-1 correspondence with staircases and modified staircases of about half the size. So for $n > 20$, I am confident the number of species is $2^{n-1} + 2^k - O(n^3)$, where $k=$ ceil$(n/2) - 1$. END EDIT 2011.07.26

EDIT 2011.07.23 Indeed, I have convinced myself that this is a relatively easily characterized class of polyominoes. I call them 4-worms, although I welcome a better term for them.

For the moment, ignore symmetry considerations and consider all orientations. First observe that staircases are part of the class that Joseph defined. Observe also that any member with n+1 squares can be gotten from a member with n squares. Finally observe that to any staircase, there are only two places to add a square which do not make a longer stair case. This makes a branch at one of the two bends at the end of the staircase; once such a branch is made, squares can only be added to the two tips at that end of the staircase because of Joseph's conditions regarding convexity and no 2x2 subfigures. So any such member of Joseph's class is a staircase with 0,1, or 2 branches.

There is a subclass of these creatures which I call crosses, which correspond to a branched staircase with at most 1 bend or 0 bends, depending on how you view the branches. Accounting for their symmetries will be a little different. For almost every other staircase, a reflection or a 180 degree rotation will produce at most one other staircase. SO the goal is to count all staircases, then count those with branches, then realize this double counts almost every such creature, so the final answer will need a division by 2 plus adding correction terms for symmetric 4-worms with symmetry group 2 and for 4-worms with symmetry groups 4 or 8, all of which belong to the crosses.

I haven't done the enumeration yet, but since all the creatures can be built by adding by squares in a certain order in at least 2 and at most 4 spots, this gives rough bounds of $2^n$ and $4^n$ for twice the number of 4-worms of size n. I suggest cutting off 2 or 4 heads of the worm, counting those arrangements, and multiply that by the number of staircases of remaining size. Crosses deserve a little more care in enumeration, but I suspect the correction term there will be asymptotically small. END EDIT 2011.07.23

Here is a thought toward computer enumeration. It still requires eliminating duplicates (which as of this writing, I see two orientations of the extended F hexomino, so it might be good to write a routine that performs the 7 transformations needed to do a comparison), but it might get a few more terms.

Because of your condition requiring no 2x2 square, the number of edges on each polyomino will be 2 + twice the number of squares in the polyomino. Because of the convexity condition, any row (in a rectilinear orientation) of squares will be contiguous. By removing an appropriate external square from an (n+1)-omino, you will get an n-omino in the same family. So I suggest doing an enumeration by adding a square to each of the n-ominoes in such a way that the conditions are met.

Further, to keep track of things, you should only add a square that does not increase the trunk length. By this I mean, if in all orientations, the maximum number of squares in a row is m, you should not add a square so as to increase that number. (You will have to make one exception to this rule, but that exception is easy to track.)

Unless the polyomino is straight, there will be at least one bend in it. So there will be for such bent polyominoes at most 2n -2 places to put the square, and it should develop that there will be much fewer places (I guess O(sqrt(n))) to put the new square.

While this method is a little challenging to do by hand, it should be easy to program. It might even be useful to generate all orientations for the purposes of enumeration or computing asymptotics, and then divide by 8 later as Timothy Chow suggests.

EDIT 2011.07.24 While I wait for Joseph to do a computer enumeration, l start the process of determining an exact count. For the moment, there are a few unwieldy cases that contribute a small order of uncertainty and a general case that makes the lower half of the bits of the count uncertain.

Observe that the creatures can be built incrementally: there is a rectilinear orientation for any creature such that it has a unique rightmost square, for if there are multiple rightmost squares, examining the squares adjacent to the rightmost squares will show that either the shape is not treelike, or it is not convex, or there is at most one square adjacent to the rightmost squares, whence an appropriate rotation will establish the orientation. The observation now results from removing this rightmost square to produce another such animal.

Now define a staircase as a polyomino which is formed in the positive quadrant in the $x-y$ plane, such that the first square covers (has lower left vertex adjacent to) the origin, and the next square if there is one is placed in the positive y direction, and afterwards one has the choice of placing the next square adjacent to the previous square in either the positive x or positive y directions. At some point we will consider symmetries of staircases and form equivalence classes of staircases and related objects. For now orientation matters in the counting.

It is clear that staircases belong to Joseph's class of interest. Some minor modifications of staircases also belong to his class. I will describe one modification, and tell you of a variation.

Let a given staircase have at least two bends. The modification involves removing a bend and forming a tee at the next bend. Suppose the staircase goes up $k+1$ squares and then over to the right for an additional $j$ squares before going up again. Take the lowest $k$ squares and move each one $j$ spaces to the right. The result now looks like (after changing coordinates and moving the origin similarly) a staircase with two fewer bends and with a branch of length $j$ extending into negative territory. (One could shift the $k$-many squares a distance smaller than $j$, but I want to consider a shift of exactly $j$, to make counting easier.) If you wish Joseph, consider this a cue to insert an explanatory figure near this paragraph.

Let me check that this modification lives in Joseph's chosen menagerie. The tree condition is preserved, as the only 2 by 2 square to be created must be at rows $k$ and $k+1$, and there is only one square in row $k$ to be had. Similarly, only the vertical line test need be applied on column $j+1$. I can't nicely describe that this passes the test, so I leave that chore to Joseph and the reader.

Looking ahead to the fact that we will divide by two later, I mention the variation now. If the staircase had three or more bends before modification, one can perform a shift at the top end of the staircase, moving a top segment either down or to the left in a way as to remove at least one bend and form a tee. Thus, for every sufficiently bent staircase, there are three variations on it which (ignoring symmetries) are also in Joseph's menagerie.

Now to argue that there are no more types of animals. Let us temporarily populate the class with all orientations of the animals. Note that by inspection, all the animals with at most 4 squares are staircases or modified staircases or are one of the other variations, or are some other orientation of what has been described. From an earlier observation, any animal with 5 squares can be gotten by adding a square in an approved fashion to an animal with 4 squares. Note by brute force or exhaustion for small $n$ that every animal with $n$ squares is an orientation of some variation of a staircase.

What is an approved addition of a square? On a staircase, it is either a lengthening which can be reoriented to another and longer staircase, or it creates a branch. On a modified staircase which has at least one tee and one bend, inspection shows that (on the branch end of the staircase) one can only add squares to the tips of the branch or the bottom step, and not to the sides of either the branch or the moved step. On a variation with two branches, only the 4 tips at the end can be lengthened.

(In the case of one tee and no other bends, one either gets a cross or an animal with two tees, which again is an orientation of a variation on a staircase.)

So we have staircases and their variations, and orientations of them, that fill the zoo, and no others. Now to count species (equivalence classes under geometric symmetries). In most cases, we will see that many species contain exactly two variations, so the number of species will be about half the number of staircases and variations. Each animal has a certain number of bends and zero, one, or two tees. In one case the tees overlap to form a four armed cross which has no bends; an animal with one tee and no bends may be called a three-armed cross.

For $n$ sufficiently large, there are floor$((n-1)/2)$ species with one bend and no tees. I will lump the straight animal one with this group and say that there are floor$((n+1)/2)$ species of crosses with two arms. Note that these come from $n-1$ distinct staircases.

There are $\binom{n-2}{2}$ staircases with precisely two bends. Applying a modification to each one gives half that many plus ceil$((n-2)/2)$ species of 3-armed crosses.

There are $\binom{n-2}{3}$ staircases with exactly 3 bends, which give rise to four-armed crosses, of which there are three different formulas for the number of species, depending on whether $n$ is 1 or 3 or even mod 4. They give an answer in or near the interval $((n-3)^3/48, (n-3)^3/24)$. I may be able to get exact numbers later.

There are $2^{n-2} - (\binom{n-1}{3} + n-1)$ remaining staircases, each with 4 or more bends. Each one of these gives rise to 3 other variations. If the number of bends is odd, a reflection maps one of the variations to another, while a 180 degree rotation is desired for an even number of bends. With few exceptions, most variations map to a distinct variation, and in so doing species are double counted. The exceptions are when there is a symmetric staircase (and so the step lengths form a palindrome), or when there is a staircase modified at both ends so that the branches are the same length, and the step lengths form a palindrome. This is roughly a square root of the total number of staircases and their variations. So a rough asymptotic is $2^{n-1} + O(2^{n/2})$ for large $n$, say $n> 10$.

I believe the sequence of counts starting with n = 1 is 1,1,2,4,10,20. Of course, for $n=7$ the count should be the answer which should be 42 (What is six times nine?), but I have not established that. END EDIT 2011.07.24

Gerhard "Ask Me About System Design" Paseman, 2011.07.22

Answer by Gerhard Paseman for Integer strings such as: 4,1,1,3,4,2,3,2

2011-07-24T05:32:56Z

What you are describing are known as Langford sequences. An Internet search will give you http://legacy.lclark.edu/~miller/langford.html and other links.

Skolem or near Skolem sequences may also be of interest to you. I have a specialization of this I am studying: see http://mathoverflow.net/questions/61744/has-anyone-seen-this-version-of-ring-toss-combinatorial-object-before .

Gerhard "Yes, Number Theory Is Involved" Paseman, 2011.07.23

Answer by Gerhard Paseman for Which graphs are zero-divisor graphs for some ring?

2011-07-23T01:17:45Z

Here is an idea which is not fully worked out. At best, it is a refinement of Gjergji's refinement. However, a negative answer would also answer Gjergji's question above, and on the other hand a construction might provide insight on building a zero divisor graph which is isomorphic to a graph for other kinds of nonzero k.

I am thinking in terms of semigroups, and have not checked that a ring will have this kind of multiplication. One major difference between 0 and a nonzero k is that nilpotent x will have all powers greater than some power equal to 0; this does not always hold for nonzero k which is a power of some x. In particular, if $x^{n+m}=x^n$ for some nonzero x and m > 1, there will be a subgraph of the graph for $x^n$ which will have at most one loop and a bunch of disjoint pairs of vertices with edges going in both directions between the members of the pair. It might be arranged in the ring that k can only be a power of x, in which case there will be no edges in the graph for k other than among powers of x. Now for the refinement: Assuming a ring exists with $x$ not nilpotent, $k= x^j$ and satisfying $x^n=x^{n+m}$, with appropriate choices for integers j,n and m, can one build a different ring with zero divisor graph matching the graph for k in this ring? I think choosing the integers mod q for some really large q will work for certain tuples of parameters j,n, and m, but I haven't checked all tuples.

Gerhard "Ask Me About System Design" Paseman, 2011.07.22

What are the chances of finding a small factor?

2011-05-07T05:07:58Z

EDIT 2011.05.09 Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates referred to below have small factors, the "large" small factors I list below are incorrect. Also, that $2^{2557} - 2^{1278} + 1$ does not have a small factor supports my "feeling" that the candidate set should have not so many small factors as I was seeming to find. I apologize for submitting such false suggestions to MathOverflow. (This post will teach me to double check my work before posting, cautious language notwithstandng.) Further updates (if any) will be near the end of this post. END EDIT 2011.05.09

Following this answer to a question of Luis Gallardo, I set my computer to look for small factors. After looking through a lot of primes, my computer suggests that $223381441$ divides $2^{2557} - 2^{1278} + 1$ and that $234355951$ divides $2^{121} - 2^{60} + 1$. The remaining exponent to be cracked is $132049$ (find a nontrivial factor or establish primality of $2^{264097} - 2^{132048} + 1$). Given that the initial candidate set was based on the $47$ known perfect numbers and that the largest of the smallest factors of all but one of them is $2^{37} - 2^{18} + 1$ (meaning that the perfect number with Mersenne exponent $19$ precedes a prime), how can I use this information to determine how likely it is that the remaining candidate has a small ($< 2^{32}$) prime factor?

(If you have a bignum package and want to do a few primality tests, I would receive that information. I would also appreciate independent verification that $42$ of the $47$ candidates are composite with small prime factors. Currently I am using 32-bit arithmetic and the moral equivalent of trial factorization to determine primality of these candidates. In spite of my initial observations that $7$ or $11$ divide most of the candidates, I am surprised at my success so far in finding small prime factors. Or should I be? That is the point of this question.)

(Also, to answer Luis's question, at this point I'd say about four or five.)

EDIT 2011.07.14 After running for several weeks, the program I had to find small prime factors finished. The major bug it had involved roundoff error, and so reported several factors which turned out not to be factors, including the two reported above and challenged (and correctly so) by Junkie.

I am independently attempting to check the factorization using the Elliptic Curve Method of $2^{2557} - 2^{1278} + 1$; that's on its 17th day currently after several restarts of the computer doing the calculations.

In addition to Charles's answer below, one can look at Hans Riesel's book Prime Numbers and Computer Methods for Factorization. The book has sections on Dickman's Theorem and on the work of Knuth and Trabb-Pardo on how prime factors are distributed according to size. END EDIT 2011.07.14

Gerhard "Ask Me About System Design" Paseman, 2011.05.06

Answer by Gerhard Paseman for How to determine all non-negative solutions to a combinatorial diophantine equation?

2011-07-11T23:57:13Z

I echo Richard Stanley in his pessimism for there being a nice formula or method for giving you the solutions. On the other hand, most of the solutions will have a_i being 0 for most of the coefficients i. Here is another way to look at it, which might help you write a program for computer search for small n.

Your constraint summing to $n$ gives that $a_i + \epsilon_i = \frac{n}{i}$, where for most $i$, $0<\epsilon_i < 2$. Since you know most $a_i$ will be zero, $s$ will be not far from a sum of terms of the form $\frac{n(i-1)}{2}$, so many solutions will be close to partitioning an integer near $\frac{2s}{n}$ into distinct parts (so e.g. a partition of 20 into {1,4,4,5,6} is not allowed). This roughening of the problem can be easily programmed without expanding the search space too much.

If you still hope for more, you might try deriving some recurrences which might help in a partial characterization of solutions. It is my feeling that a quick program can be developed that will give you the solution set for any feasible s even for n as large as 50.

Gerhard "Email Me About System Design" Paseman, 2011.07.11

Answer by Gerhard Paseman for order-preserving question

2011-07-09T23:42:54Z

In spite of not knowing whether similar means isomorphic or not, the answer seems to be no.

After an idea from Joel Hamkins, I transcribe some of the comments above.

I start the parade with: "No. Although all countable dense total orders without endpoints are isomorphic, there are countable total orders which are not dense and have one or two extrema. One example that is worth studying is the rationals x 2, which has countably many pairs (a,b) with no element c such that a < c < b. This can inject into the rationals, and the rest I leave to you as an exercise."

Part of what Stefan Geschke said: "To elaborate on Gerhard's example, any two countable linear orders that contain a copy of the rationals embed into each other. Except for containing a copy of $\mathbb Q$ they can be as dissimilar as you want."

User goldstern adds: "... whereas the embeddability and bi-embeddability structure on the countable linear orders that do not contain a copy of the rationals (so-called scattered orders) is complicated but well-investigated. (well-quasi-ordered, has exactly $\aleph_1$ classes: Richard Laver, Fraisse conjecture, 1971) "

The original poster then observes: " take A=Q\{0} and B=Q\(-1, 1), and it is easy to get two injections. "

For extra flavor, Ali Enayat remarks: "Two points: (a) the intervals [0,1] and (0,1) provide the easiest counterexample; (b) with the added hypothesis that either A or B is a well-ordering, then A and B indeed have to be similar (by Cantor's so-called Trichotomy Theorem)."

In a closely related vein, Andreas Blass provides: "Another curious point: If $A$ is order-isomorphic to an initial segment of $B$ and $B$ is order-isomorphic to a final segment of $A$, then $A$ and $B$ are order-isomorphic. (It's essential that one of the segments be initial and the other final; if both are initial then $[0,1]$ and $[0,1)$ are a counterexample.)"

I'll let someone else turn this into a Wikipedia article.

EDIT: A late arrival, "The statement in the above note of Andreas Blass is due to A. Lindenbaum and it can be found in W. Sierpinski: Cardinal and ordinal numbers, 1965, Ch. XII 9, Theorem 2. It is also in my book with Totik: Problems and theorem in classical set theory, problem 13 in ch 6. – Péter Komjáth" END EDIT

Gerhard "Please To Call It Research" Paseman, 2011.07.09

Answer by Gerhard Paseman for Groups which satisfy Mal'cev's theorem (locally residually finite)

2011-07-10T01:30:32Z

Perhaps a locally finite simple group would help? How about the subset of all even permutations of the natural numbers with finite support? Unless I am misremembering something, this should be a simple locally finite group that is not a subgroup of GL_n(k).

Gerhard "Email Me About System Design" Paseman, 2011.07.09

Answer by Gerhard Paseman for Ping-pong relief map of a given function $z=f(x,y)$

2011-07-06T18:44:46Z

This is a partial answer to Q2, and suggests to me that there is a physical arrangement which would give a yes answer to Q3.

If you use ordinary pins, you can probably get a dyadic approximation with some arrangement. Let me suggest using weighted pins as a partial solution, and then perhaps someone can implement a close enough approximation to a weighted pin with a series of dyadic pins.

So normalize things so that the function f has integral one over the interval [0,1], and is to be approximated by 2^k bins. Suppose p in [0,1] is the fraction of balls needed to represent the function on [0, 1/2], equivalently p is the integral of f from [0,1/2]. Then place a weighted pin very high such that it dumps p of the balls toward the pin over the interval [0, 1/2]. (You may want to put a divider right under this pin so that the ball doesn't jump to the [1/2,1] side.) Now recurse (k-1) more levels. Working backwards from this to get a horizontal arrangement should be clear, and of course one can use the physics of the situation to change the endpoints from dyadic rationals to something more appropriate to the desired function f.

It may be possible to emulate the bias by ever so slight horizontal adjustments of the pins, but you need to place the later pins just so that their bias accomodates the various trajectories of the incoming ball. But of course we have infinite precision pins and balls, so what's to worry?

Gerhard "Likes The Unreality of Mathematics" Paseman, 2011.07.06

Answer by Gerhard Paseman for BEST theorem for Eulerian paths with open ends

2011-07-05T22:02:27Z

The question seems to be sinking into the depths of Lethe; here is a styrofoam noodle for it.

Every Eulerian path on G can be completed to an Eulerian tour on G' which is G augmented with the edge (v,u). This correspondence is easily seen to be 1-1, so the number of desired paths on G is the formula you mention above, applied to the graph G'.

Unless I'm misunderstanding something, that should do it.

Gerhard "Email Me About System Design" Paseman, 2011.07.05

Answer by Gerhard Paseman for ${2}^{p}+{3}^{p}={a}^{n}$ , then n=1 for any p ?

2011-06-28T02:10:37Z

I was hoping to see a post by Gjergji Zaimi on this question. My guess is he deleted whatever he might have had, from which I had hoped to learn something. So I will post a start of an elementary approach in the hopes that he or someone else will finish it.

Consider the case that p is an odd positive integer. Then a must be a multiple of 5, and either n is one, or else 2^p + 3^p is a multiple of 25, in which case p must be an odd multiple of 5 by considering the sum mod 25. So in this case a^n is a multiple of 3025 if n is not 1. This can probably be refined by looking at 2^p + 3^p mod 125, and hopefully considerations mod 11 may finish it off.

Now assume p=2q for some positive integer q. If n were even we could represent 3^p by (a - 2^q)(a+2^q), which would give 3^p = 2^(q+1) + 1, which is not solvable in integers p and q. So n must be odd, a^n must be 1 mod 8 for p sufficiently large, and so must a if n is not 1. Again, more work needs to be done here. It looks plausible to me that n must be 1 if a is an integer.

Gerhard "Email Me About System Design" Paseman, 2011.06.27

Answer by Gerhard Paseman for Teaching a pedagogy course

2011-06-22T21:03:00Z

I suggest an alteration in procedure, if the department can support such. In addition to video taping and evaluating a performance which the prospective teacher T can review, offer

a) being able to sit in on the first one or two classes given by T to provide feedback to use later in the semester, or

b) better yet, assemble the prospective T's together so they can practice a day or week before they are "thrown over the wall", to borrow a phrase from software design. This can be done at the mutual convenience of the T's and perhaps one or two seasoned graduate students to help organize.

Having a timely practice session or two with copies of the material from the previous year will go much further to keep the lessons learned fresh than anything else I can imagine. It can be arranged so that the T's can do most of the work in 3 days or less. Also having a check list of common errors and common success points to use in the evaluation process would help.

Gerhard "Email Me About System Design" Paseman, 2011.06.22

Answer by Gerhard Paseman for What could be some potentially useful mathematical databases?

2011-06-21T22:51:59Z

I would like a mathematical search-thesaurus; this would be a list of descriptions people thought of to use as search terms (and that I might think of using) and for each description, a list of phrases that appeared in documents which contained stuff relevant to the descriptions. A recent example might be: "gently falling curve" yields "roller coaster physics". A prototype of a thesaurus could be built out of the MathOverflow database.

Gerhard "Searching For The Right Words" Paseman, 2011.06.21

Answer by Gerhard Paseman for Going to graduate school for mathematics next year, need some advice

2011-06-17T23:15:18Z

One of the reasons to study many courses is to gain sufficient breadth in ones education, and to have handy the information when needed. (Despite the Internet, one's brain is still handier to have, and one's perspective is important in considering applicability of knowledge. Internet resources will never be able, in my opinion, to reduce the role of perspective in determining what information is applicable and how.) Another reason is to find out what one likes and then do as much of that as compatible with one's other goals in life. So take the standard route and vary it at your own discretion; advisors and mentors may be helpful, but they need to know more of you; advice gotten from the Internet is rarely worth more than it costs to get it.

All the courses you have and more are recommended, but the pace and organization is something you and someone familiar with you and studying should work out. Also, if you have ideas on how to go about something, tell someone. One of the biggest faults I had as a graduate student was keeping too much to myself because I thought I had to be original in most everything I did. The reality of graduate school is that your work will build upon others and that one or two ideas on how to do something new, plus a lot of academic and other necessary grunt work, is what will help you get your degree or get your ideas properly recognized.

Good Luck. (Yes, sometimes luck is useful in getting a degree.)

Gerhard "Ask Me About System Design" Paseman, 2011.06.17

Comment by Gerhard Paseman

2012-09-26T21:57:12Z

How old is she educationally? (tenth grade US?, asking purely for academic purposes, not trying to fix her up.) How much time did it take (rough estimate of coding-testing-tutorial-homework breakdown would be nice to know.) Gerhard "Really, My Interest Is Educational" Paseman, 2012.09.26

Comment by Gerhard Paseman

2012-09-04T18:31:31Z

Yes... if you change your notion of "best possible" accordingly. Gerhard "Still It Makes Little Sense" Paseman, 2012.09.04

Comment by Gerhard Paseman

2012-08-30T15:36:45Z

I find some similarity between the posted problem and a lopsided version of Hall's marriage Theorem. Do you see it also? If so, there are some concerns in the infinite case, and I do not know of any constructive versions of proofs of Hall's theorem. I would be interested in your thoughts on the matter. Gerhard "Ask Me About System Design" Paseman, 2012.08.30

Comment by Gerhard Paseman

2012-08-25T22:18:03Z

Also, Westzynthius uses a similar argument to get bounds close to what Rankin and Erdos have. I will review the paper and post something summarizing the differences between W's method and the one you outline above (which may very well be no difference). Gerhard "Ask Me About System Design" Paseman, 2012.08.25

Comment by Gerhard Paseman

2012-08-25T21:46:52Z

I am still working through the literature myself, so I don't know the answer. I take it you know of the further advances on prime gap lower bounds (Pomerance, Maier, Pintz, I think?), and that they bear no resemblance to Rankin's method? Also, have you checked Hagedorn's 2009 paper on computing Jacobsthal's function to make sure there is nothing you want there? Gerhard "Just Checking On The Obvious" Paseman, 2012.08.25

Comment by Gerhard Paseman

2012-08-17T00:38:26Z

It might be prudent to try a primality test and/or a perfect power test before trial factorization or some other factorization method. If you suspect a large square factor, testing primality and or perfect power after each small factor is removed might be prudent. Gerhard "Ask Me About System Design" Paseman, 2012.08.16

Comment by Gerhard Paseman

2012-08-15T17:15:20Z

You could group terms in pairs to get terms like (1 - (n+1)a + ba^2). For small values of a this might help you with your error estimates. Gerhard "Ask Me About System Design" Paseman, 2012.08.15

Comment by Gerhard Paseman

2012-07-11T01:53:23Z

I have a feeling that f(x)=1/q^2 when x=p/q in lowest terms will be a guiding example, if not a counterexample. Gerhard "Ask Me About System Design" Paseman, 2012.07.10

Comment by Gerhard Paseman

2011-12-02T18:42:46Z

Jacques Carette has provided a nice suggestion. However, unless you specify what sort of help you need, I and others are going to think this question unsuitable for MathOverflow. (It may be unsuitable after you provide motivation or explain your difficulty, but you may get more sympathetic treatment. Also, if you have trouble with Jacques answer, you may find it best to ask on math.stackexchange instead.) Gerhard "Ask Me About System Design" Paseman, 2011.12.02

Comment by Gerhard Paseman

2011-11-28T07:43:43Z

You're right! That does look like some sort of differential equation! Uh, what is the question? Gerhard "Ask Me About System Design" Paseman, 2011.11.27

Comment by Gerhard Paseman

2011-11-28T07:31:56Z

If you still have your email address with "minasteris" in it, I will be happy to reply in brief here and in more detail by email later. It is your right to edit your post as you wish; I am with quid in that your style of frequent edits with little content change shows (to me) some lack of patience. I too suggest waiting some time (days) between successive edits. During that time, you could write down your inspiration and motivation for this and your previous questions in some detail; I will be asking about that soon. Gerhard "Ask Me About Prime Gaps" Paseman, 2011.11.27

Comment by Gerhard Paseman

2011-11-25T22:30:03Z

The above class of graphs g_r is strictly larger than what you have, so use the above class and then weed out those which obviously violate one of your desired properties. Once you see how to do that for small r, you can tell us how you do it and then we might be able to improve on the efficiency of your implementation. Gerhard "Ask Me About System Design" Paseman, 2011.11.25

Comment by Gerhard Paseman

2011-11-25T22:26:38Z

Perhaps I'm wrong, but why not try this first, and then go for efficiency after you understand the classes G_r better? This is: randomly generate the graph g_r, where g_0 is a single vertex, and for g_r+1 create the set D of 4(r+1) vertices, assign each vertex at least 1 and possibly more edges to random vertices in "the previous 4r" vertices of g_r, and then wire up D with more edges as you like? Once you understand how those look, you can try enumerating isomorphism types and generating those efficiently, at least for small r. Gerhard "Ask Me About System Design" Paseman, 2011.11.25

Comment by Gerhard Paseman

2011-11-21T01:07:54Z

Unless I am missing something, computing the sum of the kth powers of (the positive primes less than n) should be equivalent in polynomial complexity to finding all the primes less than n, when k is a positive integer. Also, it may be quick to approximate a sum of kth powers by considering the related sum for numbers of the form , say, 210m + j where j is coprime to and less than 210. Gerhard "Ask Me About System Design" Paseman, 2011.11.20

Comment by Gerhard Paseman

2011-11-19T06:42:29Z

In your exposition where you say 1 + 3n knocks out 100 etc, 3 + 7n knocks out 101, etc, I am saying -9 +3n knocks out 90 etc., -7 + 7n knocks out 91, etc. Just take away 10 mod p_i from the r_i when p_i are small enough. Gerhard "Ask Me About System Design" Paseman, 2011.11.18