User gerhard paseman - MathOverflow

Answer by Gerhard Paseman for Lower bound of the number of relatively primes(each-other) in an interval

2011-02-20T22:01:24Z

In what follows, I will have most variables ranging over positive integers (or sets of positive integers, or even sets of sets of positive integers). Let $n \gt 1$, and consider an interval $I$ of $n$ consecutive integers $[a+1,\ldots, a+n]$. Consider the subset $L$ (depending on $I$) of $P(I)$ of $I$ intersected with maximal antichains in the integer divisibility poset (actually quasi order, but most of the time will be spent in the positive integer part, which looks like a lattice; $0 \lt -a \lt n$ may be considered later), so $M \in L$ iff 1) for all $x,y \in M$, either $x=y$ or $\gcd(x,y)=1$ and 2) for all $z \in I - M$ there is $x \in M$ with $\gcd(x,z) \gt 1$ .

Since any two consecutive positive integers are coprime, one has $\card(M) \ge 2$. If $d$ is a multiple of $\pi(n)$ primorial and $d$ happens to be in $M$, then $\card(M) \lt 4$. However, in this same interval containing $d$, we can choose a set $N$ that "looks like" ${d+1, d+2, \ldots, d+p_k}$ where $k$ is $O(\pi(n))$ and $p_j$ is the $j$th (positive) prime. Based on this example, I am confident (but can not yet prove) that a lower bound for the maximum of the cardinalities of sets in $L$ is $\pi(n/2) + 1$.

UPDATE 2011.02.23 Asterios Gantzounis has done some thinking for me. He points out that the problem I have been studying shows that any proposed lower bound of the form $\pi(qn)$ where $q$ is a positive rational number will be broken. Thus $q$ cannot be a constant, but is more likely of the form $1/(u(n)\log(n))$, where $u(n) > 1$ for sufficiently large $n$ and $u(n)$ is likely a small (compared to $\log(n)$) rational function of $\log(n)$ and iterated $\log$'s of $n$. END UPDATE 2011.02.23

Now let $I_t =\{ m \in I, m $is an integer multiple of $t\}$ For any $M \in L$, we must have $\card(M \cap I_t) \lt 2$ for any prime $t$. So an upper bound for $\card(M)$ is $\pi(n) + \rho(n)$, where $\rho(n)$ is the largest number of integers relatively prime to $P_n$ (the $n$th primorial) in any subset of shape $I$ (collection of $n$ consecutive integers).

I do not have a good expression for $\rho(n)/n$, but it is related to the product $\prod_{i \le n} (1 - 1/p_i)$. I am trying to bound this product from below by $1/2\ln(n\ln(n))$, but there are some recent oscillation results by Diamond and Pintz that make me unsure when the bound actually holds. It is related to the MathOverflow question http://mathoverflow.net/questions/37679/erik-westzynthiuss-cool-upper-bound-argument-update which I will update soon (but with results modulo oscillation, rather than absolute results).

UPDATE 2011.02.25 I have posted (as an answer to the linked question above) a new estimate to the Jacobsthal function which may apply to upper bounds to this problem and to Gerry Myerson's generalization. I invite constructive comments and polite corrections regarding this estimate. END UPDATE 2011.02.25

Gerhard "Ask Me About System Design" Paseman, 2011.02.20

Answer by Gerhard Paseman for Smallest integer not divisible by integers in a finite set

2011-02-14T07:16:48Z

Thomas Hagedorn has a short survey on results related to the Jacobsthal function, as well as recent computations for a_i being the first t primes for t up to 50 . It is at http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf . In his section 1, Hagedorn cites a result of Iwaniec which gives an asymptotic upper bound of order O(t log(t))^2, and he cites a more explicit upper bound that was given by Stevens as 2t^(2 + 2elog(t)). (He also cites a lower bound by Pintz which is a mild improvement on the Erdos lower bound.) I am working on replacing the bound in Stevens' result by something asymptotically smaller (involving log(log(tlog(t))). I will post it as an answer to http://mathoverflow.net/questions/37679/erik-westzynthiuss-cool-upper-bound-argument-update when I am confident it is valid.

UPDATE 2011.02.25 I have posted an improvement of Stevens's result as an answer to the linked question above. I welcome a review of it.END UPDATE 2011.02.25

Gerhard "Ask Me About System Design" Paseman, 2011.02.13

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

2011-02-25T08:33:16Z

If someone had told me months ago that work on Jacobsthal's function provided bounds for a generalized version of this problem, I might have walked away from the problem and done nothing more. As it is, I've taught myself quite a bit, and will share some of it.

Aaron Meyerowitz was kind enough not only to do some computations for me but also to show me a better way to compute some quantities I was interested in to solve the problem. Inspired by his efforts, I convinced myself that a sequence of error terms I was using satisfied $E_{i+1}(x) \le 2E_i(x)$, which then led me to improve Westzynthius's result to $Q*2^{g(n)}$ where $g(n)$ was $n/2 + O(\log(n))$.

Aaron also pointed me towards a sequence in the Online Encyclopedia of Integer Sequences which led me to Hagedorn's 2009 paper on computing certain values of Jacobsthal's function.
http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf As a result, I have an answer to 2 of my questions and an improvement on a result in the literature. For question 1, the answer is yes, there is other work giving provable upper bounds on the order of $2^{\text{polylog}(n)}$. For question 2, the answer is also yes; a 1977 result of Harlan Stevens gives an explicit bound where an important step uses the equivalent of the Bonferroni inequalities. I looked over his argument and decided to tweak it to give an asymptotically better result. (Other work, especially by Iwaniec, give even better asymptotic upper bounds, but do not give explicit constants, so it is hard to tell precisely when those bounds are better.) I give most of Stevens' argument and some related material below.

$m$ will be a positive integer, and I prefer $m \gt 1$. Jacobsthal's function $j(m)$ gives the smallest positive integer $j$ such that, for any interval $I$ of $j$ integers of the form $[a+1,\ldots,a+j]$, it is guaranteed that one of the integers in $I$ is coprime to $m$, i.e. $\gcd(m,a+i)=1$ for at least one $a+i \in I$. Let $\text{rad}(m) = \prod_{p \text{ prime,} p \mid m} p$ be the largest squarefree factor of $m$; $j(\text{rad}(m))=j(m)$ and also $j(m)$ is the size of the largest gap between consecutive members of the set of integers which are relatively prime to $m$. In my problem above, I wanted nice upper bounds on $j(P_n)$, or Jacobsthal's function evaluated at the $n$th primorial.

There are lots of accessible results on $j(m)$. For example, if if $m_1,\ldots,m_n$ are all the distinct prime factors of $m$ (and so of $\text{rad}(m)$), and each of them is greater than $n$, then the Chinese Remainder Theorem is used in showing $j(m) \ge n+1$, and in fact for such $m$, $j(m) = n+1$. This can be generalized with a little bit of help: say $m$ and $r \gt 1 $ are such that $\sum_{1 \le i \le n} 1/m_i \lt (1 - 1/r)$. Then $j(m) \le rn$. Since it will introduce notation to be used later, I sketch a proof.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\text{ceil}(l/t) \ge J_t \ge \text{floor}(l/t)$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

One can do better, since for small primes $m_1$ and $m_2$ there may be a multiple of $m_1m_2$ inside the interval. Kanold, Jacobsthal, Erdos and others have done some improving in this area. However, I now show the result by Harlan Stevens.

Theorem (Stevens) $j(m) < 2n^{(2 + 2e\log(n))}$.

Improvement? (Paseman): For sufficiently large $n$, $j(m) \le O^*(n^{(2 +2e \log(\log(p_n)))})$.

The reasons for the $O^*$ will appear, as I will discuss Stevens's proof and the improvement together. In discussing the improvement, I will ask that $n \gt 30$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the Moebius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

$L = \sum_{t \mid m} \mu(t)J_t$.

Now Stevens cites Landau to use what I think of as a Bonferroni inequality. Breaking the sum up by $\nu(t)$, the number of distinct prime factors of $t$, one has for odd values of $s$ the following:

$L \ge \sum_{0 \le i \le s} (-1)^i ( \sum_{t \mid m , \nu(t) = i} J_t) $.

Using the estimate $\mid J_t - l/t \mid \le 1$ (except for $t=1$, when $l=J_t$),

$L \ge lT_s - SB $, where $T_s = \sum_{0 \le i \le s} (-1)^i (\sum_{t \mid m , \nu(t) = i} 1/t)$. and $SB = \sum_{1 \le i \le s} \binom{n}{s}$

Now normally one finds $s$ so that $T_s$ and $SB$ can be well estimated, and then one says that for any $l > SB/T_s$, $L$ will be positive, giving that $SB/T_s$ (or the appropriate estimate) is an upper bound for $j(m)$. Stevens doesn't do that. He instead rewrites $T_s$ as $P - T$, finds estimates for $T',P',$ and $SB'$ so that $ SB'/(P' - T') \ge SB/T_s$, ensures that $P' > T'$, and then concludes that $j(m) \le SB'/(P' - T')$. I will do the same, except I will use more refined estimates.

Let's do $SB$. Stevens's replacement is $n^s$; mine is $\binom{n+1}{s}$ times a small fudge factor, which will be strictly less than $n^s$ for $s \gt 2$ and $n$ sufficiently larger than $2s$. The small fudge factor is from dominating the sum by a geometric series with common ratio $\binom{n+1}{s-2} / \binom{n+1}{s}$. This gives $1 + (s(s-1))/((n+2)(n+3-2s))$.

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As in the question above, this gives $P = \prod_{1 \le i \le n}(1 - 1/m_i)$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

$T = \sum_{s \lt i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$ .

Now Stevens estimates $T$ by $T' > T$, first by replacing the inner sum (and throwing away $(-1)^i$), and then by having the index of the outer sum go past $n$. He then uses Taylor's theorem with remainder on $e^{h(n)}$ for a certain choice of $h(n)$ to come up with a compact term that bounds the infinite sum. Then $s$ is restricted to arrive at a $T'$ which bounds $T$ but is still small.

Here we go. For $n$ sufficiently large

$ (i!)\sum_{t \mid m , \nu(t) = i} 1/t \le (\sum_{1 \le j \le n} 1/m_j)^i \le h(n)^i$, so $T \lt \sum_{s \lt i \le n} ((\sum_{1 \le j \le n} 1/m_j)^i)/(i!)$,

so $T \lt \sum_{s \lt i } (h(n)^i)/(i!) \le e^{h(n)}(h(n)^{s+1})/((s+1)!)$.

Stevens chose $\log(n) > \sum_{1 \le j \le n} 1/p_j \ge \sum_{1 \le j \le n} 1/m_j$ for $n > 2$ to use as $h(n)$. I choose $\alpha_n + \log(\log(p_n))$ for $h(n)$, and will talk about the positive constant $\alpha_n < 1$ and the allowed values of $n$ later. (Thinking of $\alpha_n = 0.75$ is good.) Now let's get to $T'$.

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^{h(n)}2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod_{1 \le i \le n}(1 - 1/m_i) \gt \prod_{1 \le i \le n}(1 - 1/p_i) \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$. (Stevens chose $1/n$ for $P'$.) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(1/2)^{2e(\alpha_n + \log(z))}$.

Now $(1/2)^{2e\log(z)} = z^{-2e\log(2)}$. So

$P' -T' = (\beta_n z)^{-1} - (e/2^{2e})^{\alpha_n} z^{-2e\log(2) + 1} = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $

Since we will have $n$ large enough so that $\beta_n \lt (e^{\alpha_n})^{2e\log(2) - 1}$, and since $z^{2e\log(2) - 2}\gt 1$, we get that $P' - T' > 0$ .

Now to put it all together. If $s$ is odd and $s+1 \gt 2e(\alpha_n + \log(\log(p_n)))$ then

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n)$.

Now as to the choice of $\alpha_n$ and $\beta_n$. They were chosen generously: Mertens showed that $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and $\delta$ is an error bounded in size by a sum of two terms, the largest of which is $4/\log(p_n +1)$. So using Merten's estimate, $p_n + 1$ should be bigger than (some number not much larger than) $e^8$. Similarly, Mertens has an estimate on $\prod_{1 \le i \le n} (1 - 1/p_i)$, which is $e^{-(\gamma + \delta)}/\log(p_n)$, where $e^{-\gamma}$ is close to 1/1.78 and $\delta$ is bounded by a sum of three terms, the largest of which is again $4/\log(p_n+1)$, again requiring that $p_n + 1$ be bigger than (something close to) $e^8$. However, computations seem to show that the constants chosen seem to allow the rquired estimates to hold for $n \gt 30$ and some $n$ smaller than 30. The major block is on $n \gt 2s \gt 2eh(n) - 1$.

I welcome any constructive input and error checking. I will revise this in the coming weeks.

Gerhard "Almost Ready To Shelve This" Paseman, 2011.02.25

Answer by Gerhard Paseman for Applications of mathematics

2011-02-24T19:09:28Z

(Dredged up from the murky past...)

Designing control systems usually involves building a logic circuit that has several inputs and one or two outputs. Sometimes states are involved (sequencing of traffic lights, coin collectors for vending machines), sometimes not. In designing such control logic, many equations get written down which represent things like "If these three switches are off and these others are on, flip this switch over here".

Once one has the equations written down, (often as a Boolean function, a map from {0,1}^n to {0,1}) one has to build the circuit implementing these equations. Often times, the medium for implementation is a gate array, which may be a field of NAND logic gates that can be wired together, or a programmable logic device, which is like two or more gate arrays, some with ANDS, some with ORS, some NOT gates, flip-flops which are like little memory stores, and so on.

The major question is: are there enough gates on the device to build all the logic represented by the equations? To this end, computer programs called logic minimizers are used. They have certain definite rules (related to manipulation terms in Boolean logic) and certain heuristics (guidelines and methods for following the guidelines) to follow in order to minimize the number of, say, AND and OR gates used in representing the equations. The mathematics of representing any Boolean function as a series of AND and OR gates, and finding equivalent representations, has been developed and used since George Boole set down the algebraic form of what is now called Boolean Logic. Computer Science, abstract algebra, clone theory, all have played and continue to play an essential role in solving instances of this kind of problem. The fact that it is not completely solved is related to one of the Millenium Prize problems (P-NP) .

Gerhard "Ask Me About PLD Chips" Paseman, 2011.02.24

Answer by Gerhard Paseman for How to/Can you get a PhD position when you need more experience first?

2011-02-24T02:31:55Z

Here is a wild and crazy idea: answers to similar MathOverflow questions suggested going for a Master's degree en route to a Ph.D. Perhaps she (after finishing her current Masters) can enter another Master's program at the university in which she wants to do Ph.D. research. She can at least ask at that university what her chances are for trying such. (It may be possible to do cross discipline; for example a Masters in statistics or computer science might be acceptable before trying for a Ph.D. in mathematics.)

Gerhard "Thinking Outside The Normal Framework" Paseman, 2011.02.23

Answer by Gerhard Paseman for Mathematics TV clips

2011-02-24T01:19:07Z

I will be impressed if you can do better than Martin Gardner. He wrote articles meant for consumption within minutes (although not 2 or 3), and provided challenges to help maintain interest. He did articles outside of Scientific American, but I don't know that Gardner could compete for audiences that read things like People magazine.

However, many magazines publish puzzles. If the topic presented include a simple easily solved puzzle and one not so easily solved, that may draw as good an audience as anything, especially if little or no "higher reasoning" is involved. Even so, squeezing a topic into two or three minutes is a challenge. At three words a second, that is less than 600 words, which fits into a MathOverflow comment. Consider a ten minute version instead.

Gerhard "Ask Me About System Design" Paseman, 2011.02.23

Answer by Gerhard Paseman for Partitioning the integers $1$ through $n$ so that the product of the elements in one set is equal to the sum of the elements in the other

2011-02-16T08:53:33Z

I have a feeling that the answer is yes, that the representation is unique for infinitely many $n$, despite the computational evidence. Perhaps others will be similarly compelled by the observations below.

Fixing $n$, the idea is to find a subset $P$ of ${1,...,n}$ so that $\prod_{i \in P} i + \sum_{i \in P} i = n(n+1)/2 = T$. It is clear that $P$ has at least two elements which are not 1 and at most $O(\log(n))$ elements. It takes a little work to show that $\sum_{i \in P} i \lt 3n/2 + O(1)$. Rewriting $\prod_{i \in P} i = p$, and being a little sloppy, $p$ must then be in or near $[n(n-2)/2 , T - \epsilon_1]$ where $\epsilon_1$ is $O(\log(n)^2)$. So a computer search might do well to find all numbers in this interval with factors no larger than $n$. Further, if $p > T - d$, then $p$ must factorize into a product of numbers each smaller than $d$

One can go a little further and show that, if the largest factor has size $n^\alpha$, then the sum has size smaller than $(2/\alpha)n^\alpha$, so if $p$ is far enough away from $T$ then the largest element of $P$ can't be too small.

Other arguments show that if $(n-k) \in P $ for $k$ somewhat smaller than $n/2$, then there are at most one or two choices for $p$; this might be turned into a proof that $k$ cannot be in $[2,.., n/2 - \epsilon_2]$.

UPDATE 2011.02.23

Let's consider how often a partition contains (for fixed $k$) the value $n-k$ in the product. Since $k=0$ and $k=1$ are realized infinitely often, let's try $k \gt 1$.

$(n-k)*p + (n-k) + s = n(n+1)/2$, where $p$ and $s$ are the product, respectively sum, of the members of the set $P - \{n-k\}$, that is all members in the set for product which are not equal to $n-k$ . Now $s$ can range from some number greater than $\log_2(p)$ up to $p+1$, as $s$ is the sum of distinct positive integers whose product is the integer $p$. Further, $n(n+1)/2 \le (n- k+1) (p+1)$, so $p \ge (n+k-2)/2$. So when $k$ is small ($k \lt \sqrt(n+1)-1$) there aren't too many choices for $p$:

$(n+k-2)/2 \le p \lt (n+k-1)/2 + (k^2 +k)/2(n-k)$ .

So when $(k^2 + 2k) \lt n$, if $n+k$ is even, then $p$ could be $(n+k-2)/2$, otherwise $n+k$ is odd and then $p$ could be $(n+k-1)/2$.

Now we can solve for $s$: if $n+k$ is odd, $s = ( k^2 +k )/2$, otherwise $s = (k^2 + 2k -n)/2 \lt 0$ because $k$ is small. So when $k$ is small, $s$ is one of only finitely many possibilities, which means $p$ and therefore $n$ is one of only finitely many possibilities. Thus, when $k$ is fixed and not $0$ or $1$, $n-k$ can occur in a partition for only finitely many $n$. However, one can fix $k$, determine $s$, find an additive partition of $s$, multiply that partition to find $p$ and then find $n$, so there are many more $n$ for which there is more than one partition.

I still suspect that there are infinitely many $n$ for which there is not more than one partition. I also think that one can extend the above analysis for $k$ up to $n/4$ to find out exactly when $n-k$ is in a partition, but I'll let someone else run with that for now.

END UPDATE 2011.02.23

Once one finds a candidate $p$ that meets the conditions above, one still has to find a factorization of $p$ such that $p$ plus the sum of these factors adds up to $T$. I think there are enough primes and other obstacles to support the answer yes. Further, I suspect the number of such representations is bounded or if not bounded, grows slower than $\log(\log(n))$.

Gerhard "Ask Me About System Design" Paseman, 2011.02.16

Answer by Gerhard Paseman for Why semigroups could be important?

2011-02-18T18:18:24Z

Unary (1-variable) functions mapping a set X to itself under composition is a semigroup. Cayley's Theorem (one of them) says that every semigroup is isomorphic to one of this kind.

Gerhard "Ask Me About System Design" Paseman, 2011.02.18

Answer by Gerhard Paseman for is there any efficient way to compute the follow matrix equations easily

2011-02-18T09:38:58Z

Let S(j) denote the sum of the first j terms of your sum. Then S(2j-1) = S(j-1) + A^j S(j-1) A^j. So you can arrange the work so that it requires O(log k) multiplications.

Gerhard "Ask Me About System Design" Paseman, 2011.02.18

Answer by Gerhard Paseman for About Turan`s problem(inequality) in multivariable

2011-02-18T07:40:29Z

Let's try this in answer form. Let $Q = Q(x_1,\ldots,x_n)$ be a multivariate polynomial over some ordered ring containing the integers (with the usual ordering on the integers). Then define $P_n = Q - n$. Then

$(Q - (n+1))(Q - (n-1)) = Q^2 -2nQ + n^2 - 1 = (Q-n)^2 - 1$ .

This seems to satisfy your inequality, even with $A(n)= 1$ . Was there something else?

I would prefer to not find references nor do more work unless you can tell me more of what you know about the problem and more specifics on what you actually want.

Gerhard "Ask Me About System Design" Paseman, 2011.02.17

Answer by Gerhard Paseman for Is there a reason why integrals are so much easier to evaluate than sums?

2011-02-18T00:31:21Z

It depends on the object being summed/integrated. There are examples of sums that are handled by the theory of hypergeometric functions whose integrals would probably defeat most CAS systems out there.

They are different because the methods to simplify both processes are different. The focus (in American education) on the integral is because there were more examples of application in the mid 20th century. With the advent of algorithm design and applied combinatorics, more weight is being placed on evaluation of sums; even so, I think it is safe to say that integration will continue to be emphasized over summation for the near future.

Gerhard "Ask Me About System Design" Paseman, 2011.02.17

Answer by Gerhard Paseman for How many relations of length $n$ can exists in a group without enforcing shorter relations?

2011-02-17T20:46:07Z

Let w be a word (on the alphabet of the two letters plus two more symbols for the formal inverse) of length n+1. If this word is trivial, then cyclic permutations of this word are trivial and one also gets relations of the form letter = word in length n by taking a different letter out of the word and formally inverting, and rearranging the word appropriately.

When you do this you can group the cyclic permutations intp four groups (or two if you do the proper inversions). This allows you to build up lists of which words are equal. You can then do cancellation to build up shorter relations. Once you have two words of length n/2 being equal (let me assume n even for simplicity), you can now form a trivial word of length n contradictory to your premise.

Starting with K words of length n+1 no two of which are cyclically similar, one can develop K'(n+1) distinct words into two different groups. (There may be conflation and K' may be less than K; for the moment assume we are lucky and that K' = K.) If one of those groups has two words beginning (say) with the same string of n/2 letters, then you get a contradictory word, so the groups must each be smaller than 4^(n/2), giving a rough estimate of K'(n+1) <= 2 * 2^n, and more work may show that K might be of the same order as K'.

Not a full answer, and some combinatorics left to be done (for example ruling out the cases that two words have the same prefix and suffix with combined length of n/2), but I hope this line of thought helps.

Gerhard "Ask Me About System Design" Paseman, 2011.02.17

Answer by Gerhard Paseman for Diophantine problem

2011-02-16T21:14:42Z

Here is an alternative formulation (possibly your original one) where $x_m$ is replaced by $n +$ something which yields $0 < i+j+k$ with each of $i,j,k \ge -n$ . Then (I've already fixed one mistake, so check my work)

$2(i+j+k+1)n + (ij+jk +ki) = a$

$(i+j+k)n^2 + (ij+jk+ki)n +ijk = an - b$

$(i+j+k+2)n^2 - ijk = b$

Since $(ij +jk +ki)$ can be negative, we don't have $a > n$ or even $b> 0$.

However there are inequalities mentioned in other posts which apply to the terms $(s-1) = (i+j+k)$ and $t =(ij +jk +ki)$. ~~Further, one has $an/2 - b = ijk $.~~ So it might be useful to rewrite the system using $s$ and $t$ and solve it given $n$, and then see if $i,j,k$ can be found after that.

Gerhard "Ask Me About System Design" Paseman, 2011.02.16

Answer by Gerhard Paseman for Lower bound for sum of binomial coefficients?

2011-02-16T07:08:09Z

If you are willing to compute a few binomial coefficients, then (n+1) choose k + (n+1) choose (k-2) + ... + (n+1) choose (k-2l) is a good lower bound even for small l. ( I'm assuing that your summand terms should have i's where they have k's.) Of course, how good depends on how close k is to n/2, in which case one can look at differences from 2^(n/2).

Gerhard "Ask Me About System Design" Paseman, 2011.02.15

Answer by Gerhard Paseman for partitioning a number into two sets based on sum of digits

2011-02-13T05:27:00Z

The short answer is : brute force. However, there are sufficient conditions which take on the order of B choose b operations to test, where B is the radix or base of the number system ( 10 in the case of this problem ) and b is a (asymptotic with respect to the growth of B) relatively small number, on the order of sqrt(2B). So there is a good chance at a quick algorithm.

If we have the digits running from 0 to B-1, then there is for every such number a partition which has difference at most B-1 between the sums of the two submultisets. The case of a multiset of odd order is left to the reader, while the case of an even number of elements places two elements in each candidate partition so as to minimize the difference observed so far. Since the difference between the two digits is at most B-1, the difference between the sums of each partially formed partition can be arranged also to be at most B-1.

Now suppose the multiset M contains a set S of distinct digits, such that S is nice, that is S has an even sum and further S can be divided into two sets the difference of whose sums is any even number between 0 and B-1 inclusive. Then partition (M - S) as above to get a difference of less than B, and then use the appropriate partition of S to realize a partition such that the difference between the two resulting sums is at most 1.

We thus have a sufficient condition: if M contains such a nice set S, then it has a partition with difference equal to the sum modulo 2 of M. The nice thing is that a nice S is a set, and it need have about b elements in it to acheive the desired property. There may be nice multisets T of about the same size, but I do not know this.

I further suspect that most subsets of the B digits of size 2b have such a desired set S. I also suspect that these results and similar ones are in the literature, so I shan't write up much more. If someone is interested in finding how many nice subsets S there are for B up to 10 (care to try it A. M.?), I might then venture a better guess as to the size of b. I know {1,2,3,4} and {2,3,4,5} are nice for B = 10.

Gerhard "Ask Me About System Design" Paseman, 2011.02.12

Answer by Gerhard Paseman for Prime factorization of n+1

2011-02-10T17:14:57Z

Here is an elaboration on the idea. Suppose we knew the prime factorization of many numbers near n. Could we use that information in factoring n?

The one thing we can say: if k is relatively prime to (n+k), then none of the prime factors of (n+k) can be factors of n. Since there are (on average) roughly log(log n) distinct prime factors for (n+k) for small k, one would not be able to elimnate many of the pi(sqrt(n)) candidates for the smallest prime factor of n, unless n is of a special form like a Mersenne or Fermat number, which has its own theory for factorization.

So, apart from elimnating O(log(log(n))) prime factors from consideration (or providing a small factor which could be found quickly with trial factorization), knowing the prime factorization of many numbers near n itself is not likely to help. Even in the special case that n is one away from a power or a small multiple of a power still leaves a lot of work to be done.

Gerhard "Ask Me About System Design" Paseman, 2011.02.10

Answer by Gerhard Paseman for Advice on Giving a Talk

2011-02-09T06:36:27Z

Without a stated goal, giving advice seems pointless. Anyway, a good rule in general is "know your audience". Find one or two points that they might like, and pitch the talk around that.

Gerhard "Ask Me About System Design" Paseman, 2011.02.08

Answer by Gerhard Paseman for Angles in an integral lattice

2011-01-25T09:30:50Z

Let C, D be integers with C^2 < D, then C/sqrt(D) is realized in five dimensions. Hint: let w = (1,0,0,0,0) and v have first component C. There may be a way to take this down to 4 dimensions, but I am tired. Anyway, a number-theoretic characterization should not be far away for lower dimensions.

UPDATE 2011.02.07 In d <= 4 dimensions, a similar construction works, for all positive integers C and k (given k is the sum of at most (d-1) squares) for C/sqrt(k + C^2), and in dimension d = 4 it is possible to cover many of the remaining cases with w = (1,1,0,0) or (1,1,1,0). Perhaps Will Jagy can tell us which quadratic irrationals stay out of A_4 ?

Gerhard "Ask Me About System Design" Paseman, 2011.01.25

Answer by Gerhard Paseman for Open problems in Euclidean geometry ?

2011-01-30T16:50:56Z

Among the many choices one might get from an Internet search, I suggest Unsolved Problems in Geometry by Hallard Croft, Kenneth Falconer, and Richard Guy (Springer-Verlag, 1991). It may include references to non-Euclidean geometries.

As an aside, I would like to see a geometric proof that the configuration of Pappus is implied by that of Desargues for finite geometric spaces.

Gerhard "Ask Me About System Design" Paseman, 2011.01.30

Answer by Gerhard Paseman for Does any research mathematics involve solving functional equations?

2011-01-27T03:36:24Z

A clone (in universal algebra) is a (graded by arity) set of functions on a base set A, which is closed under composition and contains n-ary projection functions p_i(abar) = a_i . Determining the structure of this clone is like finding out all the functional equations that can be satisfied on A using members of the clone.

If one can determine some such relations as whether one function distributes over another, this sometimes leads to normal forms. One can then build term-rewriting systems to simplify expressions or show some terms are equal to others (unification). In practice, many problems that we want to solve (logic minimization, satisfaction) turn out to be time- or space-intractable, if not undecidable.

I submit that clone theory is the study of a suitable generalization of your question. You might look at some recent papers to see if the field is of further interest to you.

Gerhard "Ask Me About System Design" Paseman, 2011.01.26

Answer by Gerhard Paseman for Is there more than 1 way to make a 17-node graph such that there are no 4-cycles and each node has at least four edges?

2011-01-25T22:22:21Z

Here's an idea. Start with a list of all the 4-subsets of vertices and a complete graph. Start removing edges greedily to break many 4 cliques while keeping the degrees high. At some point you will have a fairly dense graph with a hopefully short list of 4-cycles remaining. You can then try nongreedy or exhaustive algorithms to produce a subgraph with no 4 cycles.

Gerhard "Ask Me About System Design" Paseman, 2011.01.25

Answer by Gerhard Paseman for What sums of equal powers of consecutive natural numbers are powers of the same order?

2011-01-24T22:23:48Z

While browsing the site http://sites.google.com/site/tpiezas/Home mentioned in the comments above, I found this on the page for cubes:

"There are many particular cubic equations with this property, one of which is $9^3+13^3+19^3+23^3 = 28^3, (9+23 = 13+19) as well as those in a nice arithmetic progression like,

11^3+12^3+13^3+14^3 = 20^3

31^3+33^3+35^3+37^3+39^3+41^3 = 66^3" .

You might ask Mr. Piezas directly for more examples.

Gerhard "Ask Me About System Design" Paseman, 2011.01.24

Answer by Gerhard Paseman for Graduate School

2011-01-24T21:41:58Z

Of course, your situation is not as mine was. If your undergraduate professors don't remember you, then it will be hard to get good letters of reference. In which case you need to develop or utilize your current relationships to get good letters of reference. For encouragement though, a brief telling of my experience follows.

I spent 5 years in industry between leaving my undergraduate institution and entering graduate school. I still had professors who remembered me and were willing to write letters of recommendation. That, combined with luck, a system for mass application (to over 70 programs, essentially down to 4 that I liked and 1 I really cared to attend), and a strong personal letter indicating a strong motivation for bringing my work experience into degree studies, was instrumental in my securing entry to graduate school. I did not need to provide references from work, but I was prepared to supply those.

One thing I could have done to improve my chances was to talk to some members of the department I liked and find out what parts of my situation would help my application. Igor Rivin seemed especially helpful in his comments and offer of time; if you get some one like that at the department you want to attend, pump then for all they are worth and repay them as appropriate, usually by thank you letters, acknowledgments in publications, and small tokens of candy or liquor or textbook or other appropriate treat. (Do this in a socially acceptable way, and not like bribing a member of an admissions committee.)

Gerhard "Ask Me About System Design" Paseman, 2011.01.24

Answer by Gerhard Paseman for Of what kind of complemented bounded poset are the structures in my quasi-variety?

2011-01-23T09:50:06Z

Here is a suggestion which favors your characterization. Assuming you characterization is correct, the main problem is to take any appropriate self-dual bounded poset with no fixed points from the involution, and show it isomorphic to a subalgebra of a power of your structure. The idea is to use some set X such as the order ideals for the poset ( or look at something which looks like the join-irreducibles in a lattice ) and map the poset into 2^X in such a way that the desired isomorphism becomes apparent. Again, the ideas come from analyzing the subdirect irreducible algebras in certain varieties (semilattices and lattices), and in results similar to the Stone representation theorem, so you may be able to borrow much from the literature.

Gerhard "Ask Me About System Design" Paseman, 2011.01.23

Answer by Gerhard Paseman for Conjecture on signed sum of integer fractions x/y from 1..N?

2011-01-18T23:30:33Z

This is a suggestion to not dismiss induction too readily.

If I were to attempt an inductive proof, one approach I would take would be an inductive definition of T(2m), the set of all sums arrived at by forming m fractions as directed and then taking all signed sums. T(2m+2) is an incremental change to T(2m), but with most likely more than exponential growth. If you can prove that T(2m) contains either fraction (2m+1)/(2m+2) or its multiplicative inverse, you can conclude S(2m+2) is 0. That would be too easy, though. I suspect you will need solve equations like x/(2m+2) + (2m+1)/y = P for some value of P that is related to a value in T(2m).

Gerhard "Ask Me About System Design" Paseman, 2011.01.18

Answer by Gerhard Paseman for Consecutive numbers with n prime factors

2011-01-18T22:59:47Z

Check out the related question http://mathoverflow.net/questions/50624/happy-new-prime-year . I have some code posted there which tracks constant sequences as well as increasing and decreasing sequences. (Check out 2302 to 2308.)

A comment made by someone else and then deleted contained the observation that multiples m of the nth primorial had s(m) >= n, so that runs of values less than n must have length less than the nth primorial. Also, if you look at multiples of 6, you get that s(m)=2 for at most 11 consecutive values instead of at most 29, so there is room for improvement in the upper bound to such lengths.

Gerhard "Reduce, Reuse, Recycle for Rep" Paseman, 2011.01.18

Answer by Gerhard Paseman for Adjacency matrices of graphs

2011-01-15T21:47:27Z

Not an answer, but something here might help. Zivkovic classifies small order (0,1) matrices by Smith Normal Form. and other measures. You might count classes to see where to look for two distinct graphs with the same SNF. http://arxiv.org/abs/math/0511636 is the paper by Miodrag Zivkovic. (Disclosure: he kindly refers to work of mine, but introduces a typo in the retelling of the argument; still, I am rather partial to this paper.)

Gerhard "Ask Me About System Design" Paseman, 2011.01.15

Answer by Gerhard Paseman for Equational logic

2011-01-13T19:40:00Z

Beyond what is taught in (American) high school algebra courses, I don't really know any beginner level treatments on equational logic. The link Ricky Demer provides a brief bibliography which includes a book on Universal Algebra and one on Mathematical Logic; browsing through your local university math library should have similar books on the same shelf that might be helpful. George Graetzer and McKenzie, McNulty, and Taylor are authors of two more books on Universal Algebra which contain a bit of equational logic, but do not say much about it as a proof system. Their focus is on Birkhoff's preservation theorem (HSP theorem) which is the main reason universal algebraists have for studying equational logic. (There are people in Theoretical Computer Science and other disciplines who have different reasons, e.g. term-rewriting systems. My exposure to Universal Algebra was more model-theoretic and not so much proof-theoretic.) I do not remember enough of the undergraduate literature to say what mathematical logic texts cover equational logic; there may be some computer science texts which do, in which case an internet book search may be more fruitful.

In addition George McNulty wrote a sort of primer in Equational Logic. Once you are familiar with the basic mechanics and want to know what recent research and work (within the last 25 years) that deals with equational logic, his survey is quite approachable.

Gerhard "Ask Me About System Design" Paseman, 2011.01.13

Answer by Gerhard Paseman for Smallest prime that does not divide the Vandermonde determinant

2011-01-05T23:55:49Z

To extend Mark Bennet's answer, one could have a_2 = a_1 + P_m, the mth primorial, giving that V is a multiple of P_m. So without parameters, there is no bound. If you want something in terms of V or the a_i, you might start with the idea that such a prime need be not much larger than the largest of (a_i - a_j), and is likely to be smaller.

Gerhard "Ask Me About System Design" Paseman, 2011.01.05

Answer by Gerhard Paseman for Computer Science for Mathematicians

2011-01-05T21:27:17Z

For those who want to go from zero knowledge to substantial breadth quickly, I recommend A. K. Dewdney's The New Turing Omnibus. Once that book is finished, tackling some of the more sophisticated books like Knuth, Aho-Hopcroft-Ullman, and the like seems more reasonable. Further, the classic books will teach CS theory that is, well, classic, and will leave the reader ill-prepared (in my opinion) for the theoretical and technological developments of this millenium. The New Turing Omnibus will prepare the reader for classic CS theory, but will not impede those who wish to learn more recent theory.

The book has influenced my writing style. One project I am working on involves "moving a mountain one pebble at a time", and is inspired by the mountain of a book Dewdney has created.

Gerhard ""Ask Me About System Design" Paseman, 2011.01.05

Comment by Gerhard Paseman

2011-02-25T23:58:23Z

I don't remember what drugs I was taking when I wrote the comment above. Will Jagy is well on his way to convincing me that C/sqrt(k +C^2) is not in A_4 if k needs 4 squares for its sum. If so, then the sufficient condition above for a number to be in A_d may also be necessary. Gerhard "Flu Medicines Have Side Effects" Paseman, 2011.02.25

Comment by Gerhard Paseman

2011-02-25T07:22:29Z

A previous answer about some (reducible) trinomial multiples of $x^2-x+1$ was deleted, taking some of my comments with it. I note that adding appropriate multiples of $x^3+1$ to $x^2-x+1$, and then dividing by $(+-1)x^k$ as desired, generates a two parameter family of trinomials (with an exponent in each residue class mod 3) whose signs depend on the added multiples, and are all multiples of $x^2-x+1$. Related to this is mathoverflow.net/questions/56579 (thanks to Mark Sapir and Gerry Myerson). Gerhard "Where Do Deleted Comments Go?" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T20:38:25Z

Many of us are stupid at times. I tried several other complex examples and missed this one. Good thing Gerry thought to post it, otherwise we might still be waiting for rescue. Gerhard "Not Lost In Thought Now" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T20:33:57Z

Yes, and I understood that. However, I thought that some ambiguity needed to be resolved. I could also read that part as, "add a given rational to the range of q_1 each time", and decided a comment to clarify was appropriate. I like the solution, by the way. Gerhard "Ask Me About System Design" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T18:25:47Z

I would say "not much use", as knowing n prime and sufficiently large gives that n+1 is even. Otherwise, I agree with your post. For more on the subject, I recommend Hans Riesels book on computer methods for factorization and primality testing. Gerhard "Ask Me About System Design" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T18:04:24Z

I'm sorry you did not understand. Did you know that x^(6k+7) - x^(6k+2) - 1 is another example? I was suggesting that this and other trinomials of a similar form ( but not exactly the same) should be considered. I hope this makes it more clear. Gerhard "Ask Me About System Design" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T17:45:07Z

I liken it to finding an absolute constant c such that ln(n) < c/(2(k-c)). This is why I think there is no such c. Gerhard "Ask Me About System Design" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T17:41:55Z

This is not considered appropriate for this forum. Check the FAQ. However, notice x_3 = (n^k)*(1 - 1/n^2)^3 and x_4 = (n^k)*(1 - 1/n^2)^4. I suspect the c you want does not exist. Gerhard "Ask Me About System Design" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T10:21:17Z

It sounds like the variables are independent, and so the minimum of the sum is the sum of the minima, in which case find the minimum for each function i, and then sum the N minima. Gerhard "Sometimes The Obvious Is Simple" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T10:01:46Z

Oh, and k=0 also works for the original trinomial. Gerhard "Helping To State The Obvious" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T09:58:55Z

Not to mention replacing x^r in any of the trinomials with -x^(r+3). Gerhard "Ask Me About System Design" Paseman, 2011.02.24

Comment by Gerhard Paseman

2011-02-24T00:05:18Z

You gave an (accepted, so presumably good) answer, and Chris Eagle gave a good comment. It's Chris's responsibility to post an answer if he wants, but a good rule is to mention in your answer something like "Inspired by Chris Eagle's comment above, I went and found ...", or "Following Chris Eagle's observation in an earlier comment, ..." . That way Chris can (vicariously) enjoy the acceptance/added reputation. Gerhard "Ask Me About System Design" Paseman, 2011.02.23

Comment by Gerhard Paseman

2011-02-23T23:58:03Z

Also, the collection closed under intersection is a semilattice. (It can be made into a lattice by adjoining at most one element, but sometimes at least one element is needed.) Gerhard "Ask Me About System Design" Paseman, 2011.02.23

Comment by Gerhard Paseman

2011-02-23T23:25:25Z

You should mention that you vary the index on q for different invocations of step 2. That way you know you are building up the range of each function so that they will each be (eventually) bijective. Gerhard "Ask Me About System Design" Paseman, 2011.02.23

Comment by Gerhard Paseman

2011-02-23T23:18:03Z

Using the updated results, one has partitions like {1,2,...,k-1,k, (2(k!) - 2k +1)} for the product, with n = 2(k!) - k + 1 , for k > 2. Gerhard "Ask Me About System Design" Paseman, 2011.02.23