User gerhard paseman - MathOverflow

Answer by Gerhard Paseman for What do we call a set that has one or fewer elements?

2012-09-20T15:57:28Z

I would explain the concept and then name it. Since the idea is to capture the uniqueness of any potential member of the set X, I would suggest describing such X as "singular". Be sure not to use "singular" for anything else in that context.

Gerhard "Caution: Alternate Words At Work" Paseman, 2012.09.20

Answer by Gerhard Paseman for Subwords of cube-free binary words

2012-09-19T19:09:03Z

I may lose my own bet. By hand I computed less than 50 binary words of length 10 that start with 0. A little less than 40 of them have 4 or 5 of the subwords. This should be easily handled by computer, and with some patience can be completed by hand. My guess is that 21 is close to the maximum, and that there will be less than 10 words of maximal length.

EDIT 2012.09.20: Here is more detail on my pseudo elegant idea mentioned in comments to the question.

Assume we are trying to make a cubefree word which avoids 011. Then after an initial block of at most two ones, our word has a subword matching the regexp ((0|00)1)*, where the subpattern repeats more than 3 times if we are getting a long such word.

Then 001001001 and 010010010 and 010101 and 101010 are other words to be avoided, so the pattern has to alternate between 00101 and 01001, but also cannot contain that pattern three times in a row. So it can have at most 5 occurrences of 00 , one of which appears in 10100101, and two occurrences of 101, otherwise a cube will appear. So the regexp repetition will happen at most 7 times, by my mental (mis?)calculation.

A similar argument appears for avoiding 011, and also avoiding 010, in which case 11 is the subpattern replacing 1 in the regexp above. A similar case for 0 occurs in the 0-1 reversal of letters for the remaining words.

By this analysis, I get 28 as an upper bound, with candidate word 1100110011011001101100110011. Unfortunately that has a cube in it, so the real bound is likely to be lower.

Again, this should be doable by hand, but Joel should verify it by computer, or deflate the above argument. END EDIT 2012.09.20

Gerhard "Just Keep Adding Another Digit" Paseman, 2012.09.19

Answer by Gerhard Paseman for Multivariable Calculus Lecture Ideas

2012-09-19T19:44:01Z

I used this more for integration and change of variables, but still you might be able to use the idea.

I took my TA section outside to a (ground level!) skylight which was a mostly transparent spherical cap with some gridlines on it. It was sunny, and you could peer down to see the shadow of the lines on the floor below. I used this as an example of how projection might change the area, and how acting on each area element needed to be considered in doing the integration. You might be able to come up with a similar visual aid for the chain rule.

Gerhard "Ask Me About System Design" Paseman, 2012.09.19

Answer by Gerhard Paseman for Cylinders dividing $\mathbb{R}^{3}$

2012-09-15T23:24:01Z

If we arrange two cylinders as a T or an L, I think one can get 7 or 8 regions with two cylinders. Also, if I have two n-gonal prisms sharing the same axis and the faces perpendicular to the axis are in the same two planes, I can still get better than 2n regions just with a small rotation.

Contrary to Joseph O'Rourke's comment (and with much less expertise than Joseph to back up my remarks), I think the geometry of surfaces will be insufficient, as I can take the 7 or 8 regions produced above, make a small rotation, and likely greatly increase the number of regions produced. There may be an eventual cubic upper bound, but I am not seeing it.

Gerhard "Ask Me About System Design" Paseman, 2012.09.15

Answer by Gerhard Paseman for A function that is defined everywhere but has unknown values

2012-09-15T20:00:10Z

It is not clear to me in what sense "known" is being used. A function I am interested in gives for input n the maximum determinant (over the reals) possible from the set of n-by-n matrices whose entries are either 0 or 1. It wasn't till a few years ago that f(14) was confirmed, even though its value was suspected for about half a century. There are other enumeration problems such as Dedekind's problem on monotonic Boolean functions for which only asymptotics are known. Perhaps a good definition of known could be provided by the poster.

Gerhard "There Is Also Jacobsthal's Function" Paseman, 2012.09.15

Answer by Gerhard Paseman for Who uses keywords (and how)?

2012-08-29T02:28:21Z

Yes, there are researchers out there that use them. Yes, there are such mechanisms for search by keyword.

I recommend you educate yourself. Go talk to a reference librarian, or one that works at your mathematics or engineering library. You will likely have your own favorite topic to search, but here are two: cleaning the tube side of heat exchangers, and representing hyperidentities by a set of finitely many identities (finite identity basis).

Gerhard "For Search By Author Use" Paseman, 2012.08.28

Answer by Gerhard Paseman for regular graph construction

2012-08-26T15:37:32Z

I do not have a general construction, but you might like playing around with this idea. Set k=b-1 and look to build a 4k+1 vertex 2k regular graph.
Begin with a cycle. If k=1, the graph is finished. Otherwise select a sequence S that "works" to give the extra edges needed. The sequence has 2k-2 integers v_i so that, choosing a direction on the cycle, vertex v gets connected to the vertex that is v_i edges further ahead in the cycle. For k=1, the empty sequence works to give a pentagon. For k=2, the sequence 4,5 works (I think) to give a nine pointed star inside a nonagon. I have not checked this, but I think the sequence 3,5,6,7 works for k=3.

Here a necessary condition is that S and its translates by adding 1 should share at most k-1 members. 4,6,7,8 has two members in common with its translate above, as does 5,7,8;9.

Gerhard "Seeing It With Shifty Eyes" Paseman, 2012.08.26

Answer by Gerhard Paseman for Consecutive composite numbers

2012-08-24T23:23:10Z

One thing I would like to see more of is an analysis of the distribution of integers coprime to a large integer (totients of?) M. If M has k distinct prime factors, one can get M/2 as an upper bound to C(k, factorial(k)/2) using the Chinese remainder theorem. You might find Jacobsthal's function (an approach to evaluating C(k,1)) a useful diversion.

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

Answer by Gerhard Paseman for Undergraduate Topology

2012-08-23T00:55:25Z

If the intent is to provide breadth, then many of the suggestions others have made are quite appealing, especially if it is made clear what branches of topology are being introduced and what a student should do outside of class to develop depth in any or all of the branches.

If the intent is to provide depth, there are likely several texts out there, one for each branch, with suggestions. I remember covering Munkres first course in Topology starting with chapter 2; even though we skipped over the set theory and foundations, I was intrigued enough by them to study set theory and foundations while in graduate school. Although the class did not go all the way through the book that first semester, we got exposed to quite a bit, and I developed more ofa taste for formalism from that class more than from any other that I took as an undergraduate.

If the intent is to provide both depth and breadth, I suggest part of it be run as a student seminar. A later toplogy course I took had me present Sard's theorem; if nothing else came from that course I at least know how to prepare to explain Sard'd theorem for my next opportunity.

Gerhard "And This Was Decades Ago" Paseman, 2012.08.22

Answer by Gerhard Paseman for Subset of edges of graph touching all vertices such that all paths consist of at most two edges

2012-08-15T20:29:39Z

You should be able to do something similar, at least for graphs with a bijection to the natural numbers. Using the bijection, take the next unprocessed vertex. If it is of degree one, move on. If it has any neighbors of degree one, remove all other edges to neighbors of degree not 1, making a disconnected star. Otherwise remove all edges incident to the vertex except for the edge leading to the smallest numbered vertex. A trans-countable version of this may also work, but you will have to come up with the limit case.

Gerhard "Ask Me About System Design" Paseman, 2012.08.15

Answer by Gerhard Paseman for Empty lattice simplex or White's theorem

2012-08-15T04:31:29Z

I have not looked at the literature, so the following may fail for some geometric reason of which I am unaware; this reflects my thinking, and I do not yet see how else to get the results.

It should be clear that (2) implies (1), so let's think about not (2) implying not (1). Then for each pair of parallel planes going through opposite edges of T, if they are lattice planes then there is another lattice plane between them that goes through T and has "as many" points of the lattice as do the parallel planes. I am hoping there is enough regularity so that the middles plane looks like one of the parallel planes shifted; perhaps I am wrong. Now we have for each pair of opposite edges of T a lattice plane going through T between the pair.

Following Sidney Harris, "And then a miracle occurs...", which means I do not know how to take the three planes intersecting the middle of T and produce a point lying in T and on the three planes, and make it a lattice point. If I were looking for a simple (and natural) proof of the result, however, this is what I would try. Perhaps I would need a map to pull the argument into Z^3 and use some analytic geometry to finish things, but I hope not.

Gerhard "Not Copying Someone Else's Catchphrase" Paseman, 2012.08.14

Answer by Gerhard Paseman for A generalization of the triangle counting problem for simple weighted graphs

2012-08-11T23:39:11Z

Here is a dumb idea. Consider processing the graph one prime at a time. This might be removing all edges with weight a multiple of p, or keeping only those that are. Do the trace computation for each induced graph and collate the results. (How? Beats me. I'm throwing out ideas with no guarantee that they will make sense, much less work.)

Here is another dumb idea, which may be good for graphs with low degree. Pick an edge. Find all valid incident edges. Count the number of triangles containing that edge. Throw out that edge. Repeat until no more triangles exist. (Perhaps the graph is not different in number of edges from a bipartite graph, in which case significant run time savings can be achieved. However, I do not know the literature on two coloring a graph with few violations.)

Gerhard "Need Good Ideas? Start Dumb" Paseman, 2012.08.11

Answer by Gerhard Paseman for what is the cycle length of the maximum normalized cycle in the directed complete graph?

2012-08-08T02:29:02Z

I'm hoping someone will take these thoughts and run with them, so that eventually the question gets answered and stops bumping to the top.

Let's set n=4 and look at 3 cycles vs 4 cycles. Arrange labeling so that 4 of the normalized values are for the 3-cycles are a,b,c,and d, and so that the following relations hold: a+b+c+d=0, and the values for 3 of the 4-cycles are 3/4 times one of (a+b), (a+c), or (-b-c). If a is the largest value, then b and c have to be smaller than a/3 and their sum bigger than -4a/3 in order for the 3 cycles to win the prize for maximal normalized value. One might be able to work out the probabilities for this case, and then make a similar comparison between pairs of k cycles and (2k-2l) cycles for judicious choices of k, l, and n. My intuition on this is poor, but it suggests to me that 4 cycles have a slight edge on 3-cycles for n=4 and even for larger n. It may be possible to build up a set of inclusion-exclusion type relations for n+1 based on the relations for n.

Gerhard "Someone Take The Baton Now" Paseman, 2012.08.07

Answer by Gerhard Paseman for Justifying/Explaining math research in a public address

2012-08-07T20:17:49Z

Perhaps I am projecting (I am about to spend a few hours writing a paper, and hope to make it very accessible while still making it appealing, but am still struggling with the planning stage), but I detect a hint of something which might result in a poor talk. That something can manifest in various ways, but I will phrase it in terms of goal management.

Some talks suffer from not achieving (for whatever reason) the goal of interesting the audience. One cause is that the speaker is interested in talking to himself/herself, to reassure themselves that what they are saying is true and interesting to them. I suspect from your remark on intellectual honesty that you are trying to avoid this or a similar pitfall, that of being so familiar with your world that you may be a poor guide and even poorer salesman or travel agent to convince others to join your world.

Some talks suffer from not achieving (for whatever reason) the goal of effectively communicating knowledge, or ideas, ore emotions, to the audience. An obvious trap is attempting to include too much detail, while a less obvious trap is showing excitemen about something while not making it clear to the audience why you are excited AND why they should also be excited.

There are other goals that could be mentioned, as well as techniques to help achieve those goals. While you do say in your post what you want to do, I have a feeling that you are taking on a little too much by talking about math research in general, and that you will end up with so many goals to achieve that you may be disappointed. If you talked about math research in a specific area, you might contrast several different modes of research and give an audience member an idea of how they might use one or more of those modes.

For example (and I am being inventive here to make a point) take efforts in number theory. There are people who will play with symbols on paper to try to find new equalities, inequalities, or other relations between objects. There are some who will take a general algebraic view and try to cast the problem using different algebraic systems to get ideas. Some will use analytic methods like calculus to get a handle on how fast functions grow or on how good an estimate of a quantity they can make. Some might use probabilistic methods to show the existence of a number with certain properties. Others might employ a geometric intuition to get a handle on such relations. Computer programs will be written and run, not to prove things but to provide evidence for or against some conjecture. Some researchers will comb the literature, trying to find related papers and assemble the pieces like a work of art to create a new result, or clarify an old one. Others will revisit the literature and provide new proofs in an attempt to improve their own understanding of what they study. (Note how quickly I generalize to activities that are common to many sciences, and I have not yet mentioned any specific ideas of geometric number theory or algebraic number theory or analytic number theory, yet the different perspectives indicate why there are at least three major branches in that field alone.)

You can talk about all the above, but if the excitement and emotional component of discovery, of repeated trial and failure aand occasional success, if those aspects are missing, much of the audience will wonder why they are there. Also, if this is something you are not passionate about, you will have a hard time communicating such passion and emotion to the audience, which I believe is key to a successful talk. Best to make sure you are very interested in what you are about to say, and not try to force it to fill the air with words.

Find some talks that you believe are good role models and borrow ideas from them; likewise remind yourself of what to do andnot do from talks that are not such good models. If you worry about the audience understanding, use common analogy honestly and freely (e.g. "It was like hitting 3 under par!", or "This approach smelled so right, it was like being in Momma's kitchen."). If you worry about the audience being bored, wake them up occasionally (perhaps with the rare joke, or an Emeril Lagasse-like "Bam! The example demolished that conjecture!", but use sparingly.)

The more I reflect on it, the more I find similarities between your situation and scripting a one hour science documentary. If you still need advice or suggestions, think about how the soundtrack of a such a documentary contributes tothe presentation, and what you can use from the approaches they take (repetition, focus, editing, splitting the story into two paths to create tension, and so on).

Enough blather; hope you find some of it useful. Good Luck!

Gerhard "Going Back To Goal Management" Paseman, 2012.08.07

Answer by Gerhard Paseman for String possible combinations

2012-08-05T20:43:55Z

If there is a lot of overlap, it may be possible to get a faster algorithm, but I doubt it. If each set has one symbol that is not in the other sets, that alone will get you n! possibilities itself. If you can tell us more about the sets, we might be able to improve upon your implementation.

Gerhard "Ask Me About System Design" Paseman, 2012.08.05

Answer by Gerhard Paseman for Consecutive integers with no large prime factors

2012-08-03T18:36:14Z

You are asking for consecutive runs of smooth numbers. I do not have the keyboard to spell Stormer with a stroke over the o, but http://en.wikipedia.org/wiki/St%C3%B8rmer's_theorem has information for you. Unfortunately, I do not know of bounds for the largest pair of consecutive smooth numbers, but perhaps you can find out and report back here. I will say that I suspect a sequence of k such numbers will not exist once you reach numbers the size of A.

Gerhard "Ask Me About System Design" Paseman, 2012.08.03

Answer by Gerhard Paseman for A prime number pattern

2012-07-30T05:22:33Z

This is implicit in Douglas Zare's comment to the problem as well as in domotorp's posted answer and the comments following, but I will make it explicit: one can substitute any slow growing sequence of integers for the primes and arrive at the same conclusion. While slow growing could be suitably generalized to some ordered groups, for the integers I will stick to there being for every positive integer n at least one member p of the sequence satisfying 2n>=p>n, and all sequence members being greater than 1.

For if we have such a slow growing sequence, then starting from any positive n, the algorithm will produce a partial sum in the interval [1 - p, p] using the term p. Now we have a loop invariant that applies to every step of the algorithm, and if the sequence has only finitely many terms less than n and they are used in decreasing order of magnitude, the invariant is maintained for each successive term p used. The conditions above show that termination yields a partial sum in [-1,2]. If you know the parity of the terms used, you can determine the parity of the result. The fact that all but one of the primes is odd explains the specific results seen by the poster.

Gerhard "Ask Me About System Design" Paseman, 2012.07.29

Answer by Gerhard Paseman for Approximate version of a balanced incomplete block diagram

2012-07-15T19:29:30Z

To expand on my comments above, an analogous problem is covering a graph by cliques. Consider the relation on the set F of files as (a,b) is in the relation if the (distinct) files a and b are to be processed. The result is like a directed graph with F as the set of vertices and the relation determining the edges. Now for p and element of the set P of processing units, you want to associate p to some of the edges. (More generally, you might assign a set or sequence of members from P to an edge to indicate how the pair of files to process.)

The setup above is general and perhaps more complex than it needs to be, but should give you ideas on how to write the code so that you can generalize when the customer asks for it. Let's simplify the picture by making the graph undirected, assigning only one processor to each edge (so a simple coloring of edges rather than a list coloring), and let's pretend that cliques are important (small subsets G of F and all edges between any two points are present ) for some reason, say optimizing disk access means a processor should stick to two disks, and G may represent a subset of the files on those two disks.

We now have a situation where we want to cover, possibly with overlap, all the edges of F (which we assume has all possible edges) by smaller cliques, perhaps of the same size. Enter the La Jolla Covering Repository: a collection of covering designs where a list of subsets of size k from a set of size v are listed so that every set of size t (for this problem, t=2), is covered or a subset of one of the sets of size k. One can divide this list among several processors to ensure all processorsto assign the tasks to be done on all pairs of files.

Since I don't like repetition, I would maintain a structure shared by all processors or used by a master to assign to a worker which would list all pairs of files and the information of which pair is being (or going to be) processed by which processor. Of course, I might change my mind depending on resource availability and problem size.

Gerhard "Or To Make Me Happy" Paseman, 2012.07.15

Answer by Gerhard Paseman for Almost all loops have a trivial automorphism group; almost all groups have a non-trivial automorphism group. What goes on in between?

2012-07-14T17:31:47Z

I suggest a general algebraic approach for this problem, since to me the major thing that is changing is the idea of 'many". Although you haven't said so, you seem to be asking about a demarcation in the lattice of varieties of algebra with one binary operation where one side has algebras with more than one automorphism versus those that have only one. The latter are called rigid, and since no nontrivial variety has only rigid algebras (think of powers), you will need to have a good technical definition of 'many'. Perhaps pseudovarieties are the classes of interest.

I recommend looking at studies of rigid algebras. If you are interested in equational formulations which promote rigidity, you could do worse than looking at versions of primal algebras, which are very rigid. The varieties they generate are called arithmetical, and therein might lie part of the answer you seek.

Gerhard "Ask Me About System Design" Paseman, 2012.07.14

Answer by Gerhard Paseman for number of zeroes in 100 factorial.

2012-07-13T03:00:07Z

It is unlikely. There are ways to compute the nth digit of certain numbers in certain bases (for example, pi in base 16) without having to compute the entire number, but in most situations, the number or formula for it either has very special properties (e.g. 101*10^n) in order to answer the question, or the work done to answer the question is tantamount to calculating the number, writing it down, and counting the digits. Not only do I know of no way to answer the question otherwise, I will wager a small amount of money that no such nice way will posted here for the next 2 years.

Gerhard "Willing To Formalize The Bet" Paseman, 2012.07.12

Answer by Gerhard Paseman for Tessellating $\mathbb{R}^n$ by bricks.

2012-07-12T20:36:06Z

I will go out on a limb and pretend I understand the question and suggest the following for an answer.

Mark's example of 1x2 bricks in two dimensions can be modified to use 1x1 bricks, perhaps at the expense of his constraint on the distance between disjoint blocks. For 3 dimensions, it should be clear that alternating layers of the same 2d pattern of cubes can be arranged so that every point belongs to at most 4 bricks, using bricks of length 3.

I submit without proof (since my multi-dimensional imager is not working at present) that for each such pattern in n dimensions, one can repeat and shift it so that each point is shared by at most (n+2) bricks of length n+1. Simply look at the points shared by most bricks in n dimensions, thicken to the next dimension, then place a brick squarely on top of such a point. It should be apparent that the layer can be shifted so that no point is shared by more than 1 more brick when a dimension is added. If the distance constraint needs larger bricks, scale the sides as needed.

At worst, this idea if wrong will give Mark an opportunity to clarify the situation.

EDIT: Now I understand the problem better. The difficulty with the above is that the constraint of each point on at most n+1 bricks when applied to the unit cube forces the offset to be smaller (1/2^n) as the dimension increases. That suggests to me that the point might need to be different distances from disjoint bricks in each dimension, which in turn suggests a quadratic lower bound for s(n). I will leave this here and update it with any better ideas I obtain. END EDIT.

Gerhard "Ask Me About System Design" Paseman, 2012.07.12

Answer by Gerhard Paseman for ULTRAINFINITISM, or a step beyond the transfinite

2012-06-30T18:14:24Z

As a sometime student of mathematical logic, I would say that the spirit of your endeavour is as old as philosophy itself. Your recasting and limiting the exercise to use work of Cantor and his formalist successors will put a perspective on the endeavour that will lead many to say that not much new will be obtained. Let me suggest some ideas to help refine or direct your considerations.

What are particular goals for such a research activity? Is a new system of numbers really needed? Suppose that such a system were created as a metric used for some property of classes of a theory expressed in second order logic. Even if you were to enhance the language with a set sized collection of symbols, the multitude of classes so described would be set sized. Even if you decide to start with some ultrainfinite class (much like one has an Infinity Axiom) and produce a large enough language, how many ways can you act on that language to define/produce new ginormous classes which would require you to invent a new system of enumeration? Unless you adopt a language and a perspective and a behaviour where everything you do is of an ultrainfinite nature, you will wind up using subscripts like 0,1,2 to describe the sequence of actions one performs to derive one class from another, and you will end up talking about set many things.

I think you will be more successful in developing a theory of ultrainfinitism if you put on the back burner any notions of relating it to the infinities of set theory, and focus on what it would be like to do unimaginably many things at the same time. For example, consider functions or relations of class-sized arity, and how they can be combined, or consider composition of a ginormous quantity of arrows in some system which bears only a mild resemblance to category theory. It is hard for me to think of doing such things and iterating them on anything away from a set-sized level, but when one has such a system or systems of multitudes in which you can do mathematics, then you or someone else can try to relate it to set-sized systems.

Gerhard "Likes Avoiding Really Big Headaches" Paseman, 2012.06.30

Answer by Gerhard Paseman for Largest graphs of girth at least 6

2012-06-28T18:40:57Z

I am collecting some varied thoughts on the problem, in the hopes that it will inspire someone to finish the problem.

I suggested earlier that the graphs in $G_{n+1}$ could be built incrementally from graphs in $G_n$ by adding one vertex and thee appropriate number of edges. Brendan McKay assured me that this would not be possible for $n=44$ as "that graph had too many edges", to reinterpret his assurance. Even so, it might be useful to consider the subgraph relation on the union of the $G$'s and see if most of them can be built up incrementally, and to characterize the ones that aren't and are primitive in some sense.

It is clear that removing one vertex and its adjacent edges from an example in $G_{n+1}$ does not reduce the minimum girth, and that adding a vertex and single edge also does not reduce the girth, so that the function $e(n)$ is increasing in $n$ for $n>4$ and further increases by no more than the minimum degree taken over all the vertices of all the members of $G_{n+1}$.

There likely is a nice argument bounding the maximum degree among all members of $G_n$, but I don't see it. I can build a graph on an even number of vertices by gluing a number of length 3 paths together at their endpoints, but this gives an average degree of slightly less than 3 and a max degree of slightly less than n/2, so this is useful more for providing a lower bound for $e(n)$ than anything else.

Another construction giving a bipartite involves associating each point in a set L with a small subset (of size 3, say) of another set R in a way that no two subsets of R so chosen intersect in more than one point. The result has girth 6 or more and if both L and R have 7 points, a maximal example resembles a BIBD (or for me, an adjacency matrix of 0's and 1's with order 7 and absolute determinant value of 24) which I believe corresponds to Brendan's example for $n=14$. Perhaps BIBD's contribute more examples? They might be a significant subclass of the primitive graphs in the subgraph relation I mention above.

Also, why so many graphs for $n=45$? It makes me think of the combinatorial explosion of equivalence classes of Hadamard matrices, although it might be better to think of equivalence classes (under row and column permutations and perhaps under switching as well) of 0-1 matrices having maximal determinant values. Are there combinatorial analogues in the literature which might suggest such a brief plethora of examples?

Gerhard "Binary Matrices On My Mind" Paseman, 2012.06.28

Answer by Gerhard Paseman for On a sum involving prime numbers

2012-06-19T18:42:13Z

You can rewrite the sum using prime gap notation. With $d_k=p_{k+1}-p_k$, the sum becomes $$ n^ap_n - \sum_{k=1}^{n-1} k^ad_k$$ and now you can use some knowledge of prime gaps to understand the last sum. For purposes of exposition I will ignore the error introduced by pretending $d_1$ is 2 even though it is actually 1. With this pretense, I can call all of the $d_k$ even numbers and with high probability assume they range from 2 to some small even number which conjecturally is at most $(\log n)^2$ but potentially at least $\log {p_n} \log{\log{p_n}}$ : let's call it Fred. I can then break up the sum into 1/2 Fred-many sums of the form $2\sum_{k \in A_i}k^a$. I will let you come up with a careful definition of $A_i$, but $A_1$ should be all the integers between 0 and n since my pretense is that all the $d_k$ are at least 2, $A_2$ will be like $A _1$ but will omit those k for which $d_k$ is exactly 2 and so on. The first sum of the 1/2 Fred-many sums is the largest and is readily computed; cf Bernoulli sums, you should get something of order $n^{a+1}$. The remaining terms get successively smaller until the sum corresponding to the maximal prime gaps is reached. You may find this perspective handy for your work, unless you derived your sum from this kind of expression, in which case, Oops.

Gerhard "Ask Me About System Design" Paseman, 2012.06.19

Answer by Gerhard Paseman for Stick knot questions: simple but may not be easy

2012-06-10T03:26:59Z

There is a problem about matching red and blue dots in the plane in pairs by straight line segments, with a length minimal matching involving no crossings. I imagine (3) could be answered negatively by similar reasoning.

Gerhard "Ask Me About System Design" Paseman, 2012.06.09

Answer by Gerhard Paseman for Covering a unit ball with balls half the radius

2012-05-28T21:06:34Z

Here is an idea which should generalize to dimensions 2 and greater. I will start with dimension 2.

Let us place a circle of radius 1/2 in the center of the radius 1 ball. We will place most, if not all, of the rest of the balls at a distance such that the center of the small ball is sqrt(3)/2 from the center of the large ball. This placement is chosen so that the angle of arc cut out of the two concentric circles is the same, which turns out to be 60 degrees. Now a convexity argument should show that every thing between the 60 degree arc on the small circle and the corresponding arc on the large circle will be covered by the same ball. The general covering problem is now reduced to a covering of the surface of the smaller (or the larger) sphere by circular caps which extend 60 degrees of arc

For n=2, this is a matter of taking the ratio 360/60. For n=3, I propose 6 caps around the equator, and for each hemisphere 6 more caps appropriately spaced with centers at latitude 30 degrees, and 6 more at latitude 60 degrees, sharing central longitude lines with the equatorial circles. Even if I messed up and two polar circles are needed, that gives a total of 33 spheres, but I think 31 balls suffice.

I am not familiar with higher dimensional sphere coverings, so I'll let someone else take over. I imagine that someone else can come up with a lower bound based on this style of arrangement. (Hey Noam Elkies, care to try out more dimensions?)

If Joseph understands this, maybe we will be graced with a few illustrations of it.

Edit 2012.05.31 I decided not to wait any longer for Noam Elkies. Here is my idea of a lower bound argument. It can probably be extended to open balls; I prefer to use compactness and closed balls for simplicity.

Let there be a covering of the closed unit ball by finitely many closed balls of radius 1/2. Any covering ball which contains the center, call it c, of the unit ball contains at most one point, call it p, on the boundary B of the unit ball. Since B minus p is open with respect to B, p is contained in one of the other covering balls which does not contain c. So we can assume the boundary B is covered by balls none of which contain c. The covering now has a finite number of balls which cover B plus at least one more ball covering c, and perhaps others.

Now replace the covering above with a new (perhaps identical) covering: shift each ball toward or away from c so as to maximize its intersection with B. This places each covering ball center at distance sqrt(3)/2 from c. B is still covered, and this new covering along with a ball of radius 1/2 placed with its center also at c is another (perhaps the same) covering with the same or fewer number of balls. Thus the posted problem is (essentially) the same as optimally covering B with caps of spherical radius of 30 degrees.

Elsewhere I noted Neil Sloane had a cover of a 3-d sphere with 20 caps each of radius slightly less than 30 degrees. I now claim an upper bound of 21 for the posted problem. Assuming Sloane's expertise with sphere packing, I expect 21 to be an exact bound. You can ask him for the covering number for dimensions greater than 3. END Edit 2012.05.31

Gerhard "Ask Me! About System Design" Paseman, 2012.05.27

Answer by Gerhard Paseman for Two definitions of graph connectedness

2012-05-14T15:42:52Z

To be more explicit, fix a vertex a and let A0 be the singleton set having a as a member. Using the mechanism of (2) and some version of the axiom of choice, define An+1 by adding the one vertex that is guaranteed to be adjacent to but not in the vertex set An. Take the union of these sets and call it A. Now either A is all of V or else something went horribly, horribly wrong. The remaining details of (1) are left to the (horrified) reader.

Gerhard "And I Do Mean Horribly" Paseman, 2012.05.14

Answer by Gerhard Paseman for Do you use the Mathematics Subject Classification (MSC) when searching for literature?

2012-05-11T15:58:14Z

If I were starting research into a field, or had to write a survey paper as a project, or recommend a breadth-oriented course of study to a student, I might do a search based on MSC codes. Usually my research interests are more focussed. Also, there are other ways of searching that would help the projects listed above.

One place where the codes might be useful is in generating glossaries by subject area. One could use a text processing system to form data points by code, number of occurrences, and so on, and use other means of preprocessing to come up with a reviewable list which could be hand annotated. I think a thesaurus for each major subject area would be quite useful, especially if it indicated historical usage.

Gerhard "Ask Me About System Design" Paseman, 2012.05.11

Answer by Gerhard Paseman for Examples of interesting false proofs

2012-04-22T03:32:13Z

The Graham Pollak theorem is discussed at this link http://mathoverflow.net/questions/5449/combinatorial-results-without-known-combinatorial-proofs/5560#5560 . I came up with a nice short and incomplete proof of it. The tricky part for me was to realize it was incomplete. Follow the commentary if you want to see my "D'oh" moment. The induction started by taking an a,b complete bipartite subgraph of an (a+b) complete graph.

Gerhard "The Induction Looked So Pretty" Paseman, 2012.04.21

Answer by Gerhard Paseman for For an approach to the Hadamard-matrix-problem: is there a proof, that the iterative plane-wise orthogonal rotations (Quartimax/Varimax) converge to global maximum?

2012-03-08T16:13:17Z

While waiting for Will Orrick to weigh in, I have an unprofessional opinion which says that this approach is unlikely to be more productive than many combinatorial approaches for finding D-optimal binary matrices.

There may be some interesting techniques used that will avoid local minima, but the problem smells to me like finding optimal minima of a function for which it can be proven that such minima are found at integral values of the arguments, but that only 1 out of every 2^(n log n) such is an actual optimal minimum. Your function has provably many global minima, and very likely exponentially more local minima. Unless you have a technique for smelling deep gopher holes ins field, you are going to end up checking a lot of shallow gopher holes. And this is for dimensions as small as n=8, where we know ahead of time what all the global minima will look like and where they will be found. If the algorithm does no better than, say, 50% success for this dimension, I expect its chances of success to be superexponentially decreasing as the dimension grows by 4.

On the plus side, I don't know about this algorithm, so there may indeed be a different smell to a deep gopher hole that this algorithm has.

Gerhard "We Need Bill Murray Now" Paseman, 2012.03.08

Comment by Gerhard Paseman

2012-09-21T01:40:44Z

Some opinions on an earlier version were rendered in another question similar to this one. The consensus was that such questions are not a good fit for MathOverflow. Gerhard "Ask Me About System Design" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T23:43:35Z

This has a smell of Frankl's union closed sets conjecture about it. Gerhard "Ask Me About System Design" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T21:18:36Z

@VCF: I think the situation is more complex than that. However, I will cast my vote and then move on. I have learned that Joseph is rather unaffected by the vote, and I appreciate the opportunity to contribute to the question and to disagree with each of you and Joseph. I look forward to more questions as well as more progress on this question. Gerhard "Agreeing To Disagree Agreefully; Agreed?" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T20:06:32Z

To be clear, square for even exponents, square and multiply one more for an odd exponent. Gerhard "Or Some Other Variation Thereupon" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T19:03:21Z

If all the axioms of an ordered ring are to be satisfied, then I think there are few choices, as (if I understand correctly) the basic orders that are discrete are determined by the order of x,y and the integers. So I suggest no such order exists that will not satisfy the universal theory. Gerhard "Ask Me About System Design" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T17:22:57Z

There are some fine mathematicians who read and reply on math.stackexchange. More relevant is that math.stackexchange has people who have recently had a similar experience to yours, and can tell you their reactions and opinions; MathOverflow, not so much. You may discover that you will need to focus on the whole you, not just the research you, to answer this question properly. Gerhard "Ask At The Other Place" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T16:23:40Z

For clarification, can someone explain why some version of lexicographic order might (or might not) work? I am thinking such an order might be where any polynomial that has a monomial containing y is greater than any polynomial that has no y whatsoever. (If on the other hand, all such orders have to respect the order on Z, then I think it unlikely such an order will be found.) Gerhard "Ask Me About System Design" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T16:07:53Z

Given the trouble Joseph has taken to help (and to further the spirit of contention), I disagree with your downvote, VCF. I will return to this later today with my voting account and give it my seventh (sixth?) vote. Gerhard "Miss Manners Might Also Disapprove" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-20T15:45:14Z

The number of cubefree words of length 30 is less than twice the 29th Fibonacci number, which is less than 10*7^6, so it is believable. Gerhard "Ask Me About Crude Estimates" Paseman, 2012.09.20

Comment by Gerhard Paseman

2012-09-19T23:01:16Z

Here is a pseudo-elegant suggestion. Suppose you look at cube free words that avoid 010. Then all blocks after the initial block will be 0, 00, or 11. Cube-free words will then have a suffix having mostly 11's. But there are only finitely many ways to avoid cubes with this restriction. Argue similarly for the other five subwords. Gerhard "I'll Take Working Over Elegant" Paseman, 2012.09.19

Comment by Gerhard Paseman

2012-09-19T21:02:49Z

And if you are gracious enough to humor me, how many regions do you get from a slight longitudinal rotation to a 3x1x1 cylinder? Gerhard "I'm Thinking You Get Ten" Paseman, 2012.09.19

Comment by Gerhard Paseman

2012-09-19T20:57:24Z

I hope you don't mind this method of asking, Joseph. VCF (in a comment to my answer) posed the possiblity of up to 8 regions with two congruent ellipsoids. For the drama of contention (and through lack of imagination) I say six. Do you know what the answer is? Gerhard "Thank You For Your Attention" Paseman, 2012.09.19

Comment by Gerhard Paseman

2012-09-19T20:44:48Z

VCF: I think you should ask Joseph's help with this one. The cylinder one was easy because I could start with two unit cylinders to get 10 regions, and then lengthen each. For the ellipsoids, I can't do that. I think 6 is the most, but Joseph has programs that can likely resolve this for you. Gerhard "My Thinking Isn't That Twisty" Paseman, 2012.09.19

Comment by Gerhard Paseman

2012-09-19T19:27:39Z

For m> 2n this should be easy. Are you looking for a formula for all m, or just for 2n >= m? Gerhard "Ask Me About System Design" Paseman, 2012.09.19

Comment by Gerhard Paseman

2012-09-19T17:04:08Z

Just computing by hand, I get less than 30 words of length 8 which begin with 0. All of these have at least 3 of the subwords of length 3, and most have 4,5, or all 6 of them. I bet by the time you get to length 12, there will be very few prefixes to check. Gerhard "I Almost Did It Myself" Paseman, 2012.09.19