User gerhard paseman - MathOverflow

Answer by Gerhard Paseman for Motivation for Frankl's conjecture?

2013-05-22T14:21:38Z

As stated, there are a couple of counterexamples F. There are no known counterexamples when X is in F and X is finite and nonempty.

I do not know of Peter Frankl's original motivation. A 1990 paper of Bjorn Poonen "On the Union-Closed Sets Conjecture" has some suggestive examples, however. Note that it holds when F is the powerset of a nonempty X, and also when F is "large enough" in the sense that the average set size of a set in F is at least half the size of X. Also (as Dustin Mixon remarks), it is a very accessible and nontrivial statement, but not like Gauss said of Fermat's Last Theorem as being one of hundreds of statements in number theory of which he could neither readily prove nor dispose.

Gerhard "Ask Me About Frankl's Conjecture" Paseman, 2013.05.22

Answer by Gerhard Paseman for Why don't more mathematicians improve Wikipedia articles?

2013-05-22T16:20:13Z

I will expand on one of Aaron Meyerowitz's remarks.

I am somewhat possessive about what I have written. Indeed one of the hurdles I had to overcome to participate on MathOverflow was to accept that what I submitted could be changed by many other people. I was upset when it happened, and the major thing that kept me from voicing that upset was the FAQ, which said other people could do that. However, most of the edits were sensitive to the thrust of the post, and turned out to be more changes to style than serious changes to content. I have grown to be more comfortable with posting answers on this forum, as my input has mainly been given due respect.

If I were a contributing author to Wikipedia, I would have to overcome a similar hurdle, especially as there would be no consensus as to what is "the" information to present. The posting would not be "mine" anymore.

If Wikipedia had a mechanism for including outside references in a useful fashion, I might be more inclined to offer material for its use. My impression of the current system is that there is a "References" section in the article which includes hyperlinks to other material. My suggestion would be to enhance this so that the link expands into essentially two documents: my version of the article, which I agree to allow Wikipedia to keep a local unedited copy and display repeatedly for their benefit, and a meta document which I agree can be modified in tandem by me and Wikipedia editors whose main purpose is to explain discrepancies, notation changes, and other elements of context to allow the reader to transition between the Wikipedia intro and my version. Wikipedia could then use (or not) my version of the article, the content of which I have control, while maintaing editorial control over their version. Even if I decided that my version was no longer appropriate, I could only petition for its removal, as I had granted Wikipedia the right to use a copy of the unedited version in perpetuity, and I have access to the meta document to say that I think a better version is available elsewhere.

It seems a little more complicated then just providing a hyperlink, but it has the advantage that it could be maintained by Wikipedia, the situation between editor and author is clearly defined and separated further, and the meta document has the flexibility to handle most of the situations that arise. Also, this kind of mechanism would accommodate my sense of possessiveness, and allow me to write things which I could use for my own purposes as well as allow Wikipedia to enhance their collection.

Gerhard "Will Write For Venti Mochas" Paseman, 2013.05.22

Answer by Gerhard Paseman for Help with this Diophantine equation

2013-05-21T15:53:17Z

Let a,b,c satisfy the restrictions given, as well as $1 + a + b + c $ is a multiple of $3$. Then $83449 + a^3 + b^3 + c^3$ is also a multiple of 3, and then $d$ can be chosen to be $1/3$ of the last quantity.

Gerhard "3D Makes It So Easy" Paseman, 2013.05.21

Answer by Gerhard Paseman for How many Perfect Matchings in a regular bipartite Graph

2013-05-20T23:36:30Z

[Placeholder until I can find the delete button. GRP]

Answer by Gerhard Paseman for How to cite a sequence from The On-Line Encyclopedia of Integer Sequences (OEIS)?

2013-05-20T20:48:23Z

To answer the question briefly: if you didn't find a guide or enough examples of a good practice online, then it is underpromoted (which includes the possibility that it doesn't exist).

People are still working on ways to cite online material, especially when referring to evolving resources like MathOverflow. If you can provide enough reference points in the bibliography to ensure that anyone who checks will find that to which you refer, then you have done your part of the job. MathOverflow assists in this by providing static unmodifiable data (question number, user number, timestamp of revision, etc.) as well as a link that gives you the data in a format suitable for bibliographic reference, but that is no guarantee that things won't change after some transition.

If OEIS had made some suggestion for reference which you still find wanting, I offer two: For the short term (while you are still active), prepare an electronic file which contains additional research notes for limited distribution. This can include your favorite online resource links or even gossip about which reference librarians to ask, but one thing it can include is a jpeg which is a screen snapshot of the OEIS page as it looked when you retrieved it. That way, for any future researcher who can't verify that part of your work and asks something like "What choo talking about Willis?", you can send them jpeg as supporting material. Hopefully they will still have a jpeg reader in that decade.

For the rest of posterity, also include links to other papers which use the sequence. Future historians can then infer the existence of a great and powerful database, something like a lost continent, which was gifted to mankind for the purpose of furthering intellectual acheivements, and which may inspire them to reconstruct it from whatever digital archives the insect rulers left to them.

Gerhard "Needs Some New Science Fiction" Paseman, 2013.05.20

Answer by Gerhard Paseman for how to proof this Stirling related equation

2013-05-17T16:42:51Z

Here is a simple approach. The left hand side (for fixed $m$) is always at most $2^m$, so when is the right hand side bigger than $2^m$? Rewriting $k = \frac{m}{d},$ this is the same as asking for which $k$ is $ek > 2^k$? By inspection or calculus, one has it true for $1 \leq k \leq 3$, so when $d$ is between $m/3$ and $m$, the inequality holds. For $d \lt m/3$, the right hand side (by Stirling) is larger than $\sqrt{2\pi d}\binom{m}{d}$, which in turn is larger than twice the largest summand on the left hand side. As has been noted elsewhere, this is an upper bound for the sum when $3d \leq m, $ showing the inequality holds for small $d$.

Gerhard "Ask Me About Rough Estimates" Paseman, 2013.05.17

Answer by Gerhard Paseman for General and translational Birkhoff lattices. Equational classes.

2013-05-16T20:19:05Z

Surely the lattice of lattice varieties is partly known. J.B. Nation is a (in some circles) well-known researcher in lattice theory, and can probably tell you much of that structure. In particular, he knows of an equation which is satisfied by all finite modular lattices, but not by all modular lattices. Such an equation can be used to build a proper subvariety of modular lattices which also properly contains all distributive lattices. I recommend a web search on "lattice of lattice varieties".

Gerhard "Not Variety Of Lattice Varieties" Paseman, 2013.05.16

Answer by Gerhard Paseman for Integers n such that sigma(n)=omega(n)n and omega(n) divides n

2013-05-14T19:05:35Z

Humbled by Dietrich Burde's example, here is my motivation for saying that there won't be many such.

Consider $\sigma(n)/n$. This is bounded above by a number I will call $P(n)$ and define as $P(n) = \prod_{0 \lt i \leq \omega(n)} \frac{p_i}{p_i - 1}$, which involves the smallest primes $p_i$. Note that when $\omega(n) \gt 4, P(n) \lt \omega(n).$ So any hope of the first equation having a solution implies that $n$ has at most 4 distinct prime factors. The case when $\omega(n)=2$ nicely captures the even perfect numbers, so let us move on to $\omega(n)=4$. Using the finer inequality $\sigma(n)/n \lt \prod_{p |n, p \text{ prime}}\frac{p}{p-1}$ gives $n = 2^a3^b5^cp^d$ for some prime p and positive integers $a,b,c$ and $d$, and further $15p/4(p-1) \gt 4$, so $p \lt 16$.

Now that we have a limit on p, we can use Zsigmondy's theorem and multiplicativity of $\sigma(p^k) = \frac{p^{k+1} - 1}{p - 1}$ to limit the exponents $a,b,c$ and $d$ to at most $6$. So there will be at most finitely many cases to check. More on the finitely many cases later.

For $\omega(n)=3$, a similar analysis implies $n=2^a3^bp^c$, although there seem to be more primes $p$ to check. However, appealing to Zsigmondy again gives bounds on the exponents, and again there will be finitely many cases.

Having exhausted myself before the exhaustive search, I will report back later with additional findings.

EDIT 2013.05.16 So I was right, but in a somewhat surprising fashion. There are finitely many cases to check, it can be done by hand, Zsigmondy's theorem can help, and there are examples, two for $\omega(n)=3,$ and one for $\omega(n)=4$.

In the 4 case, as noted above $p$ is one of $7, 11,$ or $13$, and then one computes $\sigma(p^d)$ and notes those whose prime factors fall in the set of primes at most 5. Zsigmondy's theorem says we can restrict our attention to $d \lt 5$. This leaves $p^d$ being one of $7, 11,$ or $343$. Then one computes $\sigma(q^k)$ for $q=2,3,5$ to ensure its prime power factors do not lie outside of $2^x,3^y,5^z,$ or one of the three choices for $p^d$. Zsigmondy tells us we can stop bumping up $k$ once we've seen all the small primes as factors for each $q$, which is at most 9 when $q=2$, and smaller for the other choices of $q$.

After doing this, we rule out 11 as a candidate for $p^d$, and find that $3^b=3^3$ and $5^c=5^1$, leaving $2^a$ to determine. Since $p=7$, this leads quickly to $a=5$ and $d=1$, so $30240$ is the unique example with 4 distinct prime factors.

In the 3 case, Zsigmondy tells us that if $\sigma(2^a3^bp^c) =2^a3^bp^c3 $ for some prime p, then $c$ is at most 2. This is because $\sigma(p^c)$ will be divisible by some prime larger than $3$ when $p$ is a prime larger than 3 and $c$ is larger than 2. But $\sigma(p^2)= p^2+p+1$ is odd and congruent to 3 mod 9, and cannot be of the form $2^x3^y$ for large enough $x$ and $y$. So as a result, $c=1$, and we now must have $\sigma(2^a)$ being a power of 3 or $\sigma(3^b)$ being a power of 2, each of which relates to a simple case of the Catalan conjecture (or use Zsigmondy yet again to bound either $a$ or $b$). It develops that $b=1$ and then $p \lt 9$ and one quickly finds the examples 120 and 672. END EDIT 2013.05.16

Gerhard "Off To Find More Coffee" Paseman, 2013.05.14

Answer by Gerhard Paseman for Summing ratio of ratio of partial sums of binomial coefficients

2013-05-08T06:23:43Z

$$ \sum_{m=0}^k \binom{z+1}{m} = \sum_{m=0}^k [ \binom{z}{m-1} + \binom{z}{m} ] = \binom{z}{k} + 2 \sum_{m=0}^{k-1}\binom{z}{m},$$ when $z \geq k$. So the sum can be rewritten as

$$ \sum_{z=k}^{n-1} \frac{z}{2 + \binom{z-1}{k}/\sum_{m=0}^{k-1}\binom{z-1}{m}}. $$ Let's call this summand $a_z$ . Note that $a_k = k/2, a_{k+1} = (k+1)/(2+1/(2^k - 1))$, and for small values of $j$, $a_{k+j} = (k+j)/(2 + \binom{k+j-1}{j-1}/(2^{k+j-1}-\sum_{m=0}^{j-1} \binom{k+j-1}{m}))$ . Now as z increases, the denominator of $a_z$ eventually tends monotonically to $(z+k)/k$, which means $a_z$ tends to $k$ from below. Thus the entire sum has an upper bound (for $n \gg k$) of $(n-k)k$. Further, for sufficiently large integers $l$, $a_{lk}$ is slightly larger than $lk/(l+1)$, so I imagine the actual sum differs from the upper bound by a $O(n\log{k}) $ amount.

Gerhard "Ask Me About System Design" Paseman, 2013.05.08

Answer by Gerhard Paseman for Modeling concurrent internet users

2013-05-02T20:28:41Z

If the idea is to have a toy model to "start getting your hands dirty" and gain some experience in model creation and analysis, then I can see why you would start with this particular setup. If the goal is to end up with a more refined model that gives an acceptable representation of what happens with real networks, then I am puzzled by your initial choice.

As a prelude to such a more refined model, I would analyze the case of one user issuing different requests over a span of time that was less than a day (one to eight hours, depending on the kind of user). I would have the requests overlap, so that a user could request one or more files while one is already downloading. To make things simple, leave latency and other timing issues aside and assume the router deals with passing packets to you using a FIFO queue mechanism, with whatever parameters you like for the queue. Then you can try various distrbutions to guess when the last packet of each file arrives.

The benefit of this model is that it is readily adaptable to many users: just change the distribution of requests I(y). You can also add other features to see how wait time is impacted (Hint: once you reach over 75% continuous capacity, not much additional impact will be felt).

I do not presume to know the literature to give you good recommendations; as a start though, I recommend books on queueing theory and network/communication protocol design. I recall Tenenbaum as an author on engineering texts for design of computer hardware and networks; his bibliography might be of some use.

Gerhard "Anyone Remember Gopher And WAIS?" Paseman, 2013.05.02

Answer by Gerhard Paseman for Algebras with finite essential arity

2013-04-24T21:11:06Z

I define a kind of template or macro to be used in a slightly odd fashion, not exactly typed second order logic. Let Ab(t,A,B) be the macro that expands (when appropriate inputs are given) to the logical expression (t(A,xbar) = t(A,ybar)) implies (t(B,xbar) = t(B,ybar)) . Similarly for SAb(t,B,C,D), using (t(C,xbar)=t(D,ybar)) implies (t(B,xbar)=t(B,ybar)). Now for a given algebra AA, ((for any xbar and ybar which are tuples of appropriate length built from (the underlying set of) AA, for any term t from (the set of term operations of) AA, [For any a,b from AA Ab(t,a,b) holds] )) iff AA is abelian.

Replacing the "last line" in the above with [For any b,c,d from AA Sab(t,b,c,d) holds] )) iff AA is strongly abelian gets the definition of a strongly abelian algebra as well.

There are variants of the above defintions where binary terms t(a,x) instead of larger arity terms t(a,xbar) are used, and for two congruences $\alpha \leq \beta$ of AA one can define a generalization ($\beta$ is abelian or strongly abelian over $\alpha$) using $\alpha$-related in place of = and asking for certain of a,b,c,d and the bars to be $\beta$-related. Also, once the defintion is understood for an algebra AA, it can be extended to apply to classes of algebras.

A web search for strongly abelian universal algebra leads to various papers in the literature, with Kiss, McKenzie, and Valeriote among the authors. Kiss and Valeriote in a paper on Abelian Algebras and the Hamiltonian Property mention some of the literature and note that matrix powers of unary algebras provide basic examples of strongly Abelian algebras. In another paper on strongly abelian varieties these same two authors mention the result that strongly abelian algebras have finite essential arity, and that something similar holds for locally finite strongly abelian varieties.

I know of no nice way of expressing essential arity in terms of identities. The not so nice way involves picking an integer n and then a certain set of formulas which are tantamount to saying t(abar,xbar)=t(abar,ybar), except one needs to single out the inessential variables where they live rather than conveniently grouping them together into xbar or ybar.

I have no specific example of an algebra that is not strongly abelian, but is of bounded essential arity. Here is an idea on how to build one though a finite such algebra. Take a universe of size n at least 4. (Smaller might work, but I want enough room for success.) Order the set as a chain, with 0 as the least. Create an operation of desired arity and call it b and make sure it is not strongly abelian by ensuring that b(a,xbar) is different from b(a,ybar) for at least one valuation of a, xbar,and ybar, while making it agree for c,xbar and d,ybar.

Compatible with that condition, let b have the value v satisfy that it is smaller than any of the values of its arguments, unless one of them is 0 in which case 0=b(a,ybar). Now any term which has a depth of n many b's will evaluate to 0, and be constant. If you take sufficient care, you can show that this algebra has essential arity at most w^n for w the essential arity of b.

Gerhard "Ask Me About System Design" Paseman, 2013.04.24

Answer by Gerhard Paseman for Chains or Antichains slowly increasing

2013-04-22T23:07:09Z

For $0 \leq k \lt 2^j$ , let $\sigma(k+2^j)=(2k+1)/2^{j+1}$ . Let A be a subset of integers such that $\sigma\mid_A$ is monotonic. Then $a_{n+1} - a_n$ is greater than $a_n/4$ infinitely often, which cannot hold if $a_n$ is $O(n^d)$ for any positive integer $d$.

Gerhard "Can't Make It Much Simpler" Paseman, 2013.04.22

Answer by Gerhard Paseman for smallest number of comparisons needed

2013-04-22T16:34:03Z

As Eric Tressler mentioned in the comments, you could use bucket sort which essentially means (by somehow using knowledge of f()) for each b, place b in the list at hash index f(b), then starting at the max index and looping down, use the list to update the values needed. While this does not directly compare values of f, it does assume some external ordering to the set of values which is accessible to the loop, and for me seems like an implicit comparison. Further, there are f for which you will need to loop through all the values before getting enough info to fill in for all the v_n. Even if f satisfies your condition that it is injective, you may still need to go through half the values, which for bucket sort gets prohibitive even for n above 25.

If you don't know enough about f, you have to look at all of the values to find the largest one. Once you have the set of b for which f(b) is largest, say it has s-many such b, you have enough information to fill in about n + lg(s) instances of the max subexpressions for v_n, where I use lg to be log in base 2 rounded down to the nearest integer. While it may be possible to memoize and save on f(b) comparisons, a straightforward algorithm gives the result after at most (n+1)2^n comparisons, and minor modifications might get the (n+1) factor down to (1+lgn), but not without a lot of additional comparisons of values of b or parts of b. I recommend tracking the k largest useful values to start, for some small value of k < 2n, and iterating through the necessary b. You can repeat this as often as needed to resolve unknown values of v_n.

Like Douglas Zare, I would appreciate more context. I would like to know if this is homework-related before sharing any more on this problem.

Gerhard "Ask Me About System Design" Paseman, 2013.04.22

Answer by Gerhard Paseman for Can every $\mathbb{Z}^2$ disk be pinball-reached?

2013-04-20T01:53:12Z

For small radii r, perhaps r less than 1/5, something like the following should work. I use symmetry to restrict my attention to circles in the first quadrant.

Use a checkerboard coloring and color the origin and circles with coordinates of like parity the same color, e.g silver. It should be clear that any silver circle with coordinate (0,n) or (1,n) is reachable by using n-1 reflections, and that at least 120 degrees of arc on that circle is reachable.

Now one can cover larger x coordinates by reflecting the ray off (0,n) and going up. Although the ray does not emanate from the center of (0,n), it should be clear that there is enough of the or spectrum of angles to choose from that one can use an additional reflection to hit, say, (2,n) after leaving (0,n). This should generalize to an arbitrary silver circle, and each such has at least 120 degrees of arc as an available target.

Once all the silver circles are shown to be reachable, construct a path to an arbitrary circle (m,n) by traversing to (0,n) or (0,n+1), which ever is silver, go up to a silver circle past but near (m,n), and reflect off a silver circle to the desired target.

Gerhard "Loopy After Bouncing Off Walls" Paseman, 2013.04.19

Answer by Gerhard Paseman for References on techniques for solving equations with discontinuous functions such as floor and ceiling?

2013-04-15T20:03:48Z

Joe Roberts provided the words for the calligraphed book Elementary Number Theory: A Problem Oriented Approach, which was printed in the 1970's. This book has a chapter on brackets, which in some of the number theory literature is an older name for one or both of the floor and ceiling functions. While not providing as focused a treatment of brackets, Concrete Mathematics, which was authored by Graham, Knuth, and Patashnik, also gives some service to the handling of floor and ceiling. With the bibliographies of those two books and a decent citation index, you may find more recent treatments. There may be other search terms to use, but I would start with "brackets +number theory -Lie" or something like that in a web search.

Gerhard "Is It Forty Years Already?" Paseman, 2013.04.15

Answer by Gerhard Paseman for What is "Data" involved in a mathematical construction?

2013-04-15T04:19:24Z

I don't know. However, this time I won't let that stop me from answering.

If you talk to a carpenter or a craftsman about a geometric or algebraic construction, they might look at you in a funny way, since your product is not material. Also (unless you are doing topological surgery or concatenation of words), you usually don't put parts or components together. Instead you follow a recipe of low or high level operations applied to things already constructed, which are as intangible as the result. The stuff you feed to the operations is some form of structured data, some of it numeric, some linguistic, some relational. Also during the process, you need to check that the inputs satisfy appropriate requirements, and/or that the recipe can guarantee the desired outcome.

That's why I am comfortable with the use of the word 'data', and prefer it to something like 'component' or 'subassembly'.

Gerhard "Except When It Seems Apt" Paseman, 2013.04.14

Answer by Gerhard Paseman for Square submatrix

2013-03-11T19:02:55Z

Here is a cheap lower bound. Let the first column, first row, and diagonal of a 2n by 2n matrix have zeros. Any nxn submatrix must intersect one of these lines, quickly giving $4n^2 - 6n + 2 \lt k$. This likely can be tweaked to close to $(2n-1)^2 \leq k$.

Gerhard "Ask Me About Binary Matrices" Paseman, 2013.03.11

Answer by Gerhard Paseman for All possible linear combinations of positive half-integers with coefficients +/- 1

2013-03-05T23:04:24Z

I don't know about tricky, but you can use Per's suggestion more directly. The problem is that is mu is uniform, you will have 2^n possiblities for P, and not enough memory to store them.

The idea is to compute product over i of (x^-p_i + x^p_i). If all the p_i are 1, this will have mu(P) resemble a row of Pascal's triangle, with each new row formed by adding translates of the previous row. This is the best case, since you will need to store O(n) coefficients. Hopefully, you will need as few as O(n^k) coefficients for small k, but there is the potential for exponentially many coefficients, one for each possible value of P. If the p_i occupy a small interval though, it should not be too bad.

Gerhard "Ask Me About System Design" Paseman, 2013.03.05

Answer by Gerhard Paseman for On the notion of partial semigroup

2013-03-05T16:28:44Z

I agree with Andreas Blass: the best notion depends on what you need to do. If you are going to do many general algebraic constructions, you might benefit from George Graetzer's classic textbook "Universal Algebra", which develops much theory starting from partial algebras. My hunch is he uses your 1) to build varieties of partial semigroups, but you should check it out for yourself.

Gerhard "Ask Me About System Design" Paseman, 2013.03.05

Answer by Gerhard Paseman for Faculty Handbook: Mentoring Undergraduates in Research and Scholarship

2013-03-04T06:16:06Z

I can offer some general common sense that might apply; it is derived from life experience and not from the specific setting of my mentoring undergraduates or being mentored as an undergraduate.

I find that practice is one way to develop ability in a particular skill set. I note that many of the more respected answers on this forum are not just those that are clear examples of communication: they have specific references and show quality of research and scholarship. Precision and clarity are important, but providing the links to the existing and relevant literature so that others can follow, repeat, and confirm or correct the argument presented is a hallmark of decent research; high school is not too early to start practicing such skills, even for those not destined to a profession in the sciences, engineering, or education. Even documenting and keeping journals on small projects is good practice for those aiming to produce good research. Mentors should do what they can to encourage such practice.

Gerhard "Aiming To Produce Good Research" Paseman, 2013.03.03

Answer by Gerhard Paseman for The number of specific structure

2013-02-23T17:29:21Z

I do not know the answer. However, here is part of an analysis for t=1; perhaps some of it can extend for larger t. I usually mean set of size 2t when I say set.

Consider two sets with intersection C of size t. The complement of their union has size t+1, which specifies only one set which has intersection of size t-1 with the two sets. This means any other set that intersects the two sets misses C. Thus (as t=1) one can specify a structure by listing the locations of successive C's. In this case, it means enumerating 5 cycles and dividing out by cyclic and reversal symmetry, giving 12 such structures. (I view it as 0-1 matrices where each column is proved to have 2 1's.)

It may be that taking a matrix view will help with larger t.

Gerhard "Ask Me About Binary Matrices" Paseman, 2013.02.23

Answer by Gerhard Paseman for An interesting computation related to OPNs (Odd Perfect Numbers)

2013-02-20T20:41:28Z

The polite thing would be to let Greg Martin's comment stand. However, you asked for suggestions: I think the following will help, although the tone will be less polite. I intend full respect.

1) Take a cynical (or disbelieving) view. (With your own work, that can be hard, especially after you have sweated out some result. I know. I've been there.) One such application of cynicism boils away the post down to: I(q)= 1 + 1/q < 1 +R(q)/q, where R(q) is some rational function of q such that R(q)> 1 when q>= 5. Since R(q) has magical properties, does that mean I(q) does too?

Even if R(q) gave you the exponent n that is in a nontrivial solution to Fermat's Most Famous Equation ( and tempting you to say "In Your Face!" to Andrew Wiles), it is an arbitrary choice which will not serve as an informative bound and not tell you anything more than what you have already assumed, which is that q is at least 5 and that I(q)= 1 + 1/q. If you want to link up Riemann with odd perfect numbers, using R(q) as a not provably strong upper bound won't do it. R(q) may be crucial in some other work, but your post does not show this.

If you have trouble applying cynicism to your work, get some private help. MathOverflow can help resolve technical tricky issues sometimes, but this posting is not like that.

2) Self promotion can be done in a subtle fashion on MathOverflow, and the community will not run you out on a rail. Instead of the paragraphs above referencing your work, say "In my work [1], I proved this and was moved to consider that...", followed by the technical question of interest, and a brief hyperlinked bibitem resolving [1] . I suggest editing your post to tone that aspect down.

Gerhard "Self Promotion? Who Me? Pshaw!" Paseman, 2013.02.20

Answer by Gerhard Paseman for Math Annotate Platform?

2013-02-18T02:06:17Z

If this forum were a mathematical discussion forum, your question would be welcome, encouraged, and anticipated. I would be happy to provide input from a public citizen point of view.

This forum is meant more for answers, references, and perhaps derived questions. While I hope you get some appropriate input from here, I instead encourage setting up a wiki or participating in a forum like publishing.mathforge.org, which has been discussing related issues for a while.

I believe (after gathering a few search terms from suggestions about to appear) that you will find a lot of the discussion extant on various weblogs and related fora, and that you will see a number of issues to be avoided at some cost.

As with most community efforts, you will find the greatest success coming from a dedicated subcommunity which understands and represents the core values of the effort. Assemble that, and much of the rest will follow. It is my hope that what you propose will permit and benefit from contributions from the interested public.

Gerhard "Not A Professional Mathematician (Yet)" Paseman, 2013.02.17

Answer by Gerhard Paseman for What is an ideal-supporting algebra?

2013-02-13T18:51:58Z

Something for Toby Bartels as well as the poster, I've decided to post as an answer.

A (Universal) algebra A is Hamiltonian if for every subalgebra B of A there is a congruence of A in which B is a congruence class. This is a little stronger notion than ideal-supporting. Similarly, the algebra A has the CEP (congruence extension property) if for every subalgebra B the restriction map from congruences of A to those of B is surjective, in other words every congruence th of B can be extended to a congruence ph of A so that b th c iff b ph c for all b and c in B. This is also a little stronger property than ideal-supporting.

Looking up Hamiltonian and congruence on a web search leads to a 1991 paper of Ralph McKenzie (Algebra Universalis 28, Congruence Extension, Hamiltonian and Abelian properties in locally finite varieties) on the subject. It may not be the best starting place on a quest for ideal supporting varieties, but you may find it helpful.

Gerhard "Ask Me About General Algebra" Paseman, 2013.02.13

Answer by Gerhard Paseman for Erik Westzynthius's cool upper bound argument: update?

2013-02-06T06:02:04Z

After studying Kanold's 1967 paper on Jacobsthal's function, (and being inspired by a preprint http://arxiv.org/abs/1208.5342 that I discuss below,) I found an argument, mostly very simple, which gives some nice results for the effort given. While Kanold deserves some of the credit for the argument, I have yet to see a statement by him or by anyone else that gives these results, so I present them here. (Kanold wrote several articles on Jacobsthal's function, many of which I am tracking down, which might have this argument. I am happy to accept help in obtaining electronic copies of them.) This is the post I promised over a few months ago in a supplement to a question of Timothy Foo, http://mathoverflow.net/questions/88323/analogues-of-jacobsthals-function .

For maximum ooh-aah effect, I assume $n$ is squarefree and has $k \gt 2$ prime factors, one of which I call Peter, or $p$ for short.Now $1+tn$ is coprime to $n$ for any integer $t$. So are most integers of the form $1 + tn/p$, the exceptions being those that are multiples of $p$, and those multiples do not occur as consecutive terms. Thus, every interval of length $2n/p (=g(p)n/p)$ has at least one integer coprime to $n$ of the form $1+tn/p$.

Let's go further with this. Let $d \gt 1$ and divide $n$, and let $f=n/d$. (Here I use $n$ squarefree to get $f$ coprime to $d$.) Then numbers of the shape $1+tf$ form an arithmetic progression, are coprime to $f$, and (as can be seen by multiplying by $f$'s inverse in the ring of integers mod $d$) you can't pick $g(d)$ consecutive members of this progression without hitting something coprime to $d$ also. So $g(n) \leq g(d)f = g(d)n/d$ .

While I'm here, let me sharpen the inequality, assuming $f \gt 1$ and $d \gt 1$ are coprime: there are $\phi(f)$ totients $c$ of $f$ in the interval $[0,f]$, so I can repeat the argument with $c+tf$ instead of $1+tf$. In the worst case, using all $\phi(f)$ progressions, I get $g(fd) \leq g(d)f - f + g(f)$, which mildly improves upon Kanold's bound $g(d)f -\phi(f)+1$, and matches it when $f$ is prime. (Of course, for $n=fd$ I really want $g(n)$ to be near $O(g(d)+g(f))$, but I don't yet know how to show that with grade school arithmetic.)

How to use this inequality? Pick the largest divisor $d$ for which one can comfortably compute (a subquadratic in $k$ upper bound for) $g(d)$; I pick $d$ to contain most of the large prime factors of $n$: find prime $q$ dividing $n$ so that $\sigma^{-1}(d)=\sum_{p \text{ prime,} p|n, p \geq q} 1/p$ is less than $1 + 1/2q$; a routine argument yields $g(d)$ is $O(qk)$. The ugly part is to show that $q \lt k^{0.5}$ (or else $d=n$), that $n/d \lt 2^{3q/2}$ which for large $k$ approaches $2^{3(k^{\epsilon + 1/e})/2}$, and that asymptotically $g(n)$ is $O(e^{k^{1/e}+D\log(k)})$. This isn't hard after using one of Mertens's theorems and a Chebyshev function; it just isn't pretty. (Also for smaller $n$, $\epsilon + 1/e$ can be close to $1/2$, but with patience $\epsilon$ will tend to zero.)

This gives a bound that is asymptotically better than my first efforts at this, improves slightly ($k^{0.5}$ replaced by $Ck^{0.37}+ D\log(k)$ on Kanold's bound of $2^\sqrt{k}$ for $k$ not too large, and does not need Kanold's requirement that $k > e^{50}$. Up until one chooses $d$ and crunches the formulae, it is also a very elementary argument; I suspect even Legendre knew about using the multiplicative inverse to transform a general arithmetic progression to a (effectively) consecutive sequence of integers and still preserve the property of interest here, being a unit in a certain ring (or missing it by that much).

(One of the benefits of letting this sit for a few months before posting is that I can add cool observations like: If I could get the inequality down to $g(n) \leq g(d)g(n/d)$, I could iterate the above simple estimate to get an explicit bound of $O(k^c)$, where $c$ is a positive number less than 3. Or like: using more advanced work combined with the above, I can get $g(n) \leq e^{k^{e^{-a}}}Ck^{a}$ for some integers $a$, which seems better than $Ck^{4\log\log{k}}$ if you don't look too closely.)

Further, one can use a computer to refine the method slightly and get estimates which do quite well for small values of $n$, where small here means $k<100$. Asymptotically though, Stevens's and my upper bounds eventually outperform this bound.

Also, there has been a nice result out of University College Dublin that I will briefly interpret. Fintan Costello and Paul Watts find a way of presenting a related function recursively, then numerically compute a lower bound on this function which implies an upper bound on Jacobsthal's function computed on some particular values. I thank them for reminding me about using a multiplicative inverse mod $d$ for $f$, so they deserve a "piece of the action".

These authors work in (and sometimes away from) the integer interval $BM = [b+1,b+2,\ldots,b+m]$. Given squarefree $n$ and its distinct prime factors, listed in some order as $q_1$ to $q_k$, define $Q_i$ as $\prod_{0 \lt j \leq i} q_j$. One approach to computing the size $\pi(b,m,n)$ of the set $CP(b,m,n)$ which has those integers in $BM$ coprime to $n$ is to do the standard inclusion-exclusion argument: if we represent by $F(b,m,d)$ the multiples of $d$ in $BM$, and say there are $f(b,m,d)$ many such multiples, and abuse some notation, I then write $CP(b,m,n) = \sum_{d | n} sgn(d,F(b,m,d))$ . Here $sgn$ is to suggest adding elements of the set $F(b,m,d)$ if $d$ has an even number of prime factors, and subtracting them instead when $d$ has an odd number of prime factors.

To set up for the recurrent expression, Costello and Watts use just some of the terms on the right hand side of the abused equation, and reorganize the rest of the terms. In my interpretation of their work, they start with the multiset identity

$$CP(b,m,n) \cup \biguplus_{0 \lt i \leq k} F(b,m,q_i) = BM \uplus \biguplus_{0 \lt i \lt j \leq k} RCP(i,j)$$

where $RCP(i,j)$ is $F(b,m,q_iq_j) \cap CP(b,m,Q_{i-1})$, or the subset of $BM$ which has those multiples of $q_iq_j$ whose soonest prime factor in common with $n$ is $q_i$.

One sees this identity holds by considering a member of $BM$ which has exactly $t$ distinct prime factors in common with $n$. If $t$ is $0$, then the member occurs only once in $CP(b,m,n)$ and similarly only once in $BM$. Otherwise, it occurs exactly $t$ times in the left hand side in $t$ distinct terms $F(b,m,q_i)$, and if $l$ is soonest such that $q_l$ is a prime factor of the member, the member occurs only once in each of $t-1$ sets $RCP(l,j)$ (remember $l$ comes sooner than $j$) and only once in $BM$.

Now the term $RCP(i,j)$ is a subset of an arithmetic progression $A$ with common difference $q_iq_j$. By using the technique above of multiplying by a suitable inverse of $q_iq_j$ in the ring of integers mod $Q_{i-1}$, $A$ corresponds with an integer interval starting near some integer $c_{ijbm}$ of length $f(b,m,q_iq_j)$ which preserves the coprimality status with respect to $Q_{i-1}$: to wit, the size of $RCP(i,j)$ is $\pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$. Using the $\pi$ term for the size of $CP$ and translating the other sets to numbers gives the numerical recurrent formula of Costello and Watts: $$\pi(b,m,n) = m - \sum_{0 \lt i \leq k} f(b,m,q_i) + \sum_{0 \lt i \lt j \leq k} \pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$$.

Following work of Hagedorn who computed $h(k)=g(P_k)$ for $k$ less than 50, where $P_k$ is the $k$th primorial, Costello and Watts use their formula and some analysis of coincidence of prime residues to compute an inequality for $\pi_{min}(m,n)$ which is the minimum over all integers $b$ of $\pi(b,m,n)$. They underestimate $f(b,m,q_iq_j)$ by $\lfloor m/q_iq_j \rfloor$, ignore the $c$'s by using $\pi_min$, pull out the $i=1$ terms from the double sum and rewrite that portion to include a term $E$, depending only on $m$ and the $p_i$, which arises from looking at when estimates for the sizes of the $F(b,m,p_i)$ and $F(b,m,2p_i)$ sets can be improved, and come up with (a refined version, using $p$'s for $q$'s, of) the inequality $$m - \sum_{0 \lt i \leq k} \lceil \frac{m}{p_i} \rceil + \sum_{1 \lt i \leq k} \lfloor \frac{m}{2p_i} \rfloor + E + \sum_{1 \lt i \lt j \leq k} \pi_{min}(\lfloor \frac{m}{p_ip_j} \rfloor,P_{i-1}) \leq \pi_{min}(m,P_k)$$.

With this inequality, Costello and Watts compute $\pi_{low}$, a lower bound approximation to $\pi_{min}$. Since $h(k) \leq m$ iff $\pi_{min}(m,P_k) \gt 0$, computing $\pi_{low}(m,P_k)$ for various $m$ will give an upper bound on $h(k)$. They say their computations for $k \leq 10000$ suggest $h(k) \leq Ck^2 \log k$, where $C$ is a constant less than $0.3$ . Although this data is achieved using data from Hagedorn's work, even without that their algorithm yields values which are a vast improvement on known and easily computable bounds, even the ones listed above.

One item to explore is how an algorithm based on this approximation will perform given different orderings of the prime factors. I suspect that letting the larger primes come first will give tighter results. Another item to explore is to see if there is a better term $F$ that will supplant $E$ and some of the recurrent terms in the double sum. The idea of rewriting the $\pi$ function recursively, while not new, is given new life in this double sum form, and suggests revisiting some old approaches with an eye toward computability.

Gerhard "Ask Me About Coprime Integers" Paseman, 2013.02.05

Answer by Gerhard Paseman for Presenting a paper: Do's and Don'ts?

2010-06-29T05:35:16Z

Practicing your presentation helps. With a recording device or a test audience, you can get valuable feedback concerning the style and timing of your presentation, among other things.

In addition to verbally presenting a paper, there is supplementing the presentation.

Sometimes the interested audience member will want more. You might prepare ahead of time some business cards, or even slips of paper, to hand out. They should contain your contact information, the title and time of your talk, and optionally a URL to a file that contains details of your presentation that you would like to have given. This is one of the things I will do for my 15 minute presentation. If you are really on top of things, you could have something ready to receive the member's contact information as well.

Gerhard "Ask Me About System Design" Paseman, 2010.06.28

Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways

2011-03-07T08:36:34Z

To clarify Aaron's observations: since the original post asked for something to be true in every interval (of consecutive integers) of length P_n, the residue classes are indeed a red herring. The Chinese Remainder Theorem says that there will be a number common to all those residue classes, and therefore the problem will look the same whether the classes are nonzero residues or not, since we are dealing with finitely many primes.

This now turns into a problem of Jacobsthal's function on numbers of the form (P_N/P_n), where P_N is the product of all primes less than P_n, which in turn is the product of all primes less than n. Jacobsthal's function asks for the length j(m) of the smallest interval of integers which guarantees at least one integer coprime to m, i.e. lies outside the desired residue classes. Aaron is right when he requests that the sum of the reciprocals of the primes involved should be greater than 1. My computation suggests this starts to happen when n=5, p_n= 11, P_n = 2310, and there are roughly 340 (+ or - 20) primes involved in the product (P_N/P_n). I am trying to refine estimates to decide if j(P_N/P_n) is less than or equal to or greater than 2310. My instinct tells me greater, and that this will hold true for n> 4. I will update this later with the computations. In the meantime, you can try to use the upper bound estimates in the recent answer I posted to my Westzynthius question on MathOverflow.

Gerhard "Ask Me About Coprime Intervals" Paseman, 2011.03.07

Answer by Gerhard Paseman for Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations?

2011-03-05T20:25:52Z

The exercise in Algebras, Lattices, Varieties Volume I by McKenzie, McNulty, and Taylor may be of interest: There is a term t(x,y,z) in three variables in the language of one binary symbol which is universal in the sense, that, given an infinite set A and a ternary operation G(x,y,z) on the set A, there is a binary operation on A such that, when t is constructed out of this binary operation, then G(x,y,z) = t(x,y,z) for all triples x,y,z from A. Note that the term t specified is independent of A or G. I do not know if universality is defined for tuples of terms (I would be expect that serious side conditions need to be present in order for a tuple of terms to represent uniformly a tuple of operations of the same arity, thus making it not so universal).

For the question regarding whether a given countable family of operations can be built from one operation, this is a consequence of asking if the clone generated by the family of operations is generated by one operation. Given that there are uncountable many clones on a 3-element set, I would say that the question is of interest but unlikely to be solvable uniformly or even nicely. By this I mean, if Q(F) is some way of expressing that the family F generated a clone which is finitely generated, I can imagine necessary condtions implied by Q(F) and sufficient conditions which could imply Q(F), but nothing which would be equivalent. (The question of whether F is contained in a finitely generated clone might be easier, but I do not know how much easier.)

You probably have better access to references on clone theory than I; you might try pursuing those first before asking me for a further opinion.

Gerhard "Ask Me About System Design" Paseman, 2011.03.05

Answer by Gerhard Paseman for paper rejected because not so general

2011-02-27T23:17:47Z

I think that you need a second (and perhaps third) opinion from a professional. If possible, write some individual emails requesting people to give a quick impression as to the publication-worthiness of your result. Since the result is on ArXiv, no question of precedence should arise. You can ask the author you asked before for names of other people to ask. It is important that you emphasize that you don't need them to spend time going over the paper (if all you need is a quick impression; for a more thorough review, you will want a different strategy of approach).

Please note: MathOverflow is a place for specific questions. If you have trouble with a particular proof, you can ask about that detail. Zev Chonoles is right in commenting that MathOverflow is not a place to solicit reviewers for your work. Pablo Shmerkin is (somewhat) right in the idea that it is smart to include a link to your ArXiv submission, in case someone is interested and volunteers to review it. (In short: Asking for review on MathOverflow, bad; making it possible using less than 100 characters without asking, not so bad, and possibly priceless.)

Gerhard "Will Rewrite Commercials For Barter" Paseman, 2011.02.27

Answer by Gerhard Paseman for Happy New Prime Year!

2010-12-30T00:28:05Z

I decided to share this awk code to compute s(n), primarily because I like that it uses only addition and the distributive law, and not factoring, to compute s(n). It also uses a bit of string processing and hash-table look up, but is a nice example of the use of associative arrays. I also like it because it uses $O(\pi(n)\log(n))$ bytes of memory, essentially one entry per prime number less than n. Apologies to sleepless in beantown: I prefer obfuscated awk and nice algorithms to one-liners in Perl, so do not accept his challenge made in a comment on his answer.



BEGIN{  LIM = 10000 ; SEP = "," 
prev = count[1] = count[2] = count[3] = SENTINEL = 0
dir[1] = 1 ;        dir[2] = 0 ;        dir[3] = -1
str[1] = " / at " ; str[2] = " = at " ; str[3] = " \\ at "
notify[1] = notify[3] = 3; notify[2] = 6

for( n = 2 ; n < LIM ; n++ ) { # cmp means composite
  if (n in cmp) {  split(cmp[n], fl, SEP) ;  delete cmp[n] }
  else { # n is prime; make up factor list from scratch
     fl[1] = n ; fl[2] = SENTINEL }
  for(f = fl[j=1] ; f != SENTINEL ; f = fl[++j] ) {
     if ((nn = (n+f)) in cmp) cmp[nn] = f SEP cmp[nn]
     else cmp[nn] = f SEP SENTINEL }
  s = j - 1  

for (k in dir) { count[k] = (prev == (s - dir[k]))?(count[k] + 1): 1
    if (count[k] > notify[k]) print count[k] str[k] n ":" s }
  prev = s
} }

Sample output verifies the results of sleepless in beantown, plus shows that there are long runs where s is constant: 2=s(2302)=...=s(2308) . It suggests that there is a function f(s) such that there are at most f(s) consecutive numbers with value s. I suspect f(1)=4, but do not yet have a proof.

Gerhard "Ask Me About System Design" Paseman, 2010.12.29

Comment by Gerhard Paseman

2013-05-25T07:09:18Z

There is sum of products form, for a start. Or did you have something else in mind? Gerhard "Ask Me About System Design" Paseman, 2013.05.25

Comment by Gerhard Paseman

2013-05-25T06:56:18Z

You should also recall that universal algebra in the 40's and 50's was quite a bit different than a mere two decades later. I am far from being an expert in the history of even specialized subjects as model theory or universal algebra, but the only concepts I can recall studying from that time are related to Birkhoff's HSP theorem or his and related studies in lattice theory. From my perspective, "not yet mature" is an understatement. Also, what were they using it for? My memory yields no French scholars from that time in the field. Gerhard "Or Anywhere Close To Logic" Paseman, 2013.05.24

Comment by Gerhard Paseman

2013-05-25T06:40:33Z

For asymptotics, an upper bound on the number of k generated semilattices may help you. For labeled elements, the number is something like doubly exponential ($2^{2^k}$). For lower bounds look at general tree enumeration and consider trees wth k leaves and k+n vertices for n much smaller than k. Gerhard "Ask Me About System Design" Paseman, 2013.05.24

Comment by Gerhard Paseman

2013-05-25T05:54:37Z

The intriguing aspect of this is that he requires R(a,b) before "augmenting" R; just having R(a',b) is not enough. This makes it different (and more restrictive) than many constructs that augment relations similarly. It is barely possible that Tarski might have considered something like this, and that Steve Givant would know of a reference. Perhaps Joel could bring this to Steve's attention? Gerhard "Thinks Tolerances May Also Relate" Paseman, 2013.05.24

Comment by Gerhard Paseman

2013-05-24T22:24:46Z

Perhaps I am also not seeing things. Why is the answer not k=N+1? Gerhard "Someone Make A Constraint Visible" Paseman, 2013.05.24

Comment by Gerhard Paseman

2013-05-24T17:40:20Z

The output is of type real, not of type integer. Gerhard "How Is The Choice Used?" Paseman, 2013.05.24

Comment by Gerhard Paseman

2013-05-24T15:52:26Z

Usually, just seeing your name attached to a question is enough for me, Joseph. This time I ask for more on how this particular dynamics arose. Were you considering the period 5 dynamic that goes (for a rational f acting on the previous two terms that escapes me) a, b, f(), f(f()), f(f(f())), f^4=a,f^5=b? Gerhard "Suspicious Minds Want To Know" Paseman, 2013.05.24

Comment by Gerhard Paseman

2013-05-23T16:45:47Z

Clear, not clea. Also, the second case leads to $2^{a-2}(l^2 - 2) = l - 1$, from which one notes that $a \gt 3$ gives no positive integer solutions for $l$. Gerhard "Also Likes Working With Inequalities" Paseman, 2013.05.23

Comment by Gerhard Paseman

2013-05-23T16:39:13Z

I find it more clea to say "In the first case,$l = 2^{a-2}k+1$, so $2^{a-2}k^2 + k = 2^{a-1}-1$, thus $k^2 \lt 2$ and $a \lt 4$.", and come up with an analogous expression and similar bound on $a$ in the second case. Nice argument. Gerhard "Likes Working With Small Numbers" Paseman, 2013.05.23

Comment by Gerhard Paseman

2013-05-23T15:28:47Z

I recommend k going from 1 to ab. Gerhard "Index Checking Is Always Worthwhile" Paseman, 2013.05.23

Comment by Gerhard Paseman

2013-05-23T14:46:34Z

If you remove the inequality restriction in your Theorem statement, you can get some non well ordered sequences for some choices of f, e.g. floor of log of x+y+1 or a suitable modification thereof. Gerhard "Ask Me About Growing Slow" Paseman, 2013.05.23

Comment by Gerhard Paseman

2013-05-22T22:42:03Z

Note that if it is true for n=2, then it is true for all n, by using a hypersphere of well chosen irrational radius with all the lattice points sitting in a two dimensional subspace. Gerhard "Irrational Solutions To Rational Problems" Paseman, 2013.05.21

Comment by Gerhard Paseman

2013-05-22T22:29:36Z

Ryan, not if the sphere is not centered at the origin. Gerhard "Ask Me About System Design" Paseman, 2013.05.21

Comment by Gerhard Paseman

2013-05-22T20:30:28Z

Note that the question mentions sequences and not solutions. Can you modify it to count the leaves under each major branch of the search tree? Gerhard "Ask Me About System Design" Paseman, 2013.05.21

Comment by Gerhard Paseman

2013-05-22T19:57:32Z

My rusty memory says that Frankl brought it up in a conference in 1979, and that it might even appear in proceedings. I saw Dwight Duffus and we discussed the problem briefly; my impression was that he learned of it early on and credited it to Frankl, and that it was not originally a conjecture of Duffus. However, this impression is almost twenty years old, and subject to error. Gerhard "Memories From A Previous Millenium" Paseman, 2013.05.21