User mike spivey - MathOverflow

Answer by Mike Spivey for How to solve a specific multivariate recurrence relation (or general ones)

2012-11-29T23:53:17Z

I get $$f(a,b) = \frac{ (1-np)^b n!}{(n-a)!} \sum_{j=0}^b \binom{b}{j} \left\{ j \atop a \right\} \left(\frac{p}{1-np}\right)^j,$$ where $\left\{ j \atop a \right\}$ is a Stirling number of the second kind. I tested the formula in Mathematica against your recurrence for different values of $n$ and $p$, and they agree. Unfortunately I'm having trouble pasting the Mathematica input and output that verifies that agreement on this site without it turning into gobbledygook.

To get the formula I used Theorem 6 (which is actually due to Neuwirth) in my paper "On Solutions to a General Combinatorial Recurrence," Journal of Integer Sequences 14 (9): Article 11.9.7, 2011. The paper is about solution techniques for solving certain multivariate recurrences. Your recurrence happens to be in one of the forms for which the techniques work.

There might be a way to simplify the summation involving binomial coefficients and Stirling numbers, but I don't see it right now.

Added: The formula I used is the following.

Theorem. Suppose $R(n,k)$ satisfies the recurrence $$(\alpha(n-1) + \beta k + \gamma)R(n-1),k) + (\beta' + \gamma')R(n-1,k-1) + [n=k=0].$$ Then $$ R(n,k) = \left(\prod_{i=1}^k (\beta' i + \gamma') \right) \sum_{i=0}^n \sum_{j=0}^n \left[ n \atop i \right] \binom{i}{j} \left\{ j \atop k \right\} \alpha^{n-i} \beta^{j-k} \gamma^{i-j}.$$ (Here, $0^0$ is taken to be $1$.)

For the OP's recurrence, we have $\alpha = 0, \beta = p, \gamma = 1-np, \beta' = -p,$ and $\gamma' = (n+1)p$.

Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4

2012-01-28T21:46:38Z

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of $4$ is given by $2^n \binom{n}{n/2}$. Can someone provide a combinatorial proof of this fact?

Background: A few months ago on math.SE I asked for a combinatorial proof of the identity $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2},$$ when $n$ is even.

The non-alternating version is $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n.$$ There are several combinatorial proofs of the non-alternating version, and I hoped to adapt one of them. One such proof is that $\binom{2k}{k} \binom{2n-2k}{n-k}$ counts the number of paths of length $2n$ with $2k$ steps above the horizontal axis and $2n-2k$ steps below it. Summing up over all values of $k$ gives the total number of paths of length $2n$, which is $2^{2n} = 4^n$. (I believe I saw this argument in Feller's An Introduction to Probability Theory and Its Applications. It's also in this note by David Callan.)

If we take the alternating version, the paths with positive parity are those with $2k$ steps above the axis for $k$ even, and the paths with negative parity are those with $2k$ steps above the axis for $k$ odd. For each path, break it every time it returns to the horizontal axis. This partitions each path into a number of segments equal to the number of times it returns to the axis. For every path that has a last segment consisting of $2j$ steps for $j$ odd, flip this segment over the horizontal axis. This mapping is an involution and changes the path's parity. Since every odd-parity path must have at least one such odd segment, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k$$ must count the number of paths that have no odd segment; i.e., the number of paths whose returns to the horizontal axis occur only at multiples of $4$. If $n$ is odd, there are no such paths without an odd segment, but if $n$ is even, there are apparently $2^n \binom{n}{n/2}$ of them.

However, I was unable to find an independent combinatorial proof that $2^n \binom{n}{n/2}$ counts the number of lattice paths of length $2n$ with no odd segments. (Again, an "odd" segment here is one of length $2j$, where $j$ is odd.) The math.SE question remained unanswered for over two months until I found a different way to prove the identity I was after combinatorially, but this other way doesn't involve lattice paths. After all the time I spent trying the lattice path approach I would like to see an independent combinatorial proof that $2^n \binom{n}{n/2}$ counts the number of lattice paths whose return times to the axis are multiples of $4$.

Maximum vertical distance for a lattice path when NSEW steps are allowed

2011-12-29T16:55:43Z

Suppose we have a lattice path in 2D starting at the origin, in which north, south, east, and west steps are allowed. For a given path $L$, let $\max(L)$ be the maximum value of the $y$ coordinate achieved by $L$ over the length of its path. For example, the path NENWSWW would have $\max(L) = 2$.

What is known about the distribution of $\max (L)$ over all paths of length $n$?

(It seems like this problem would have been studied, but most of the results on lattice paths I've found allow only north and east steps. Perhaps I'm not using the right search terms.)

Clarification: My question is that if we list all possible paths of length $n$, and sort them by the value of $\max (L)$ for each path, how many are there with $\max (L) = 0, \max (L) = 1,$ etc.? If we think about this from a random walk perspective, it's equivalent to imposing a uniform distribution on the four possible steps at each point.

When does a triangle of numbers have a zero row sum?

2010-12-09T17:54:34Z

What general conditions exist that imply, for all sufficiently large $n$, $$S(n) = \sum_{k=0}^n \left| n \atop k \right| = 0?$$

There are two that I know of.

First: If $g(n,k) = -f(n,k-1)$ then the recursion immediately yields a zero row sum.

Three examples, for $f(n,k) = 1, f(n,k)= k$, and (more esoterically) $f(n,k) = (k+1)(2n-k-2)(2n-k-3)$, respectively: $$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0, \text{ for } n \geq 1,$$ $$\sum_{k=1}^n (-1)^k (k-1)! \left\{ n \atop k \right\} = 0, \text{ for } n \geq 2,$$ $$\sum_{k=0}^{n} (-1)^k k!(2n-k-2)!\left\langle\left\langle n\atop k\right\rangle\right\rangle=0, \text{ for } n \geq 2,$$ where $\left\langle\left\langle n\atop k\right\rangle\right\rangle$ is a second-order Eulerian number. (The third identity appears in this question and was partly the inspiration for my question.)

Second: If $f(n,k) + g(n,k) = q(n)$ (i.e., independent of $k$) and $q(n) =0$ for some $n$, then $\sum_{k=0}^m \left| m \atop k \right| = 0$ for all $m \geq n$.

(See, for example, Theorem 17 of Neuwirth, "Recursively defined combinatorial functions: Extending Galton's board," Discrete Mathematics, 2001. This result states that if $f(n,k) + g(n,k) = q(n)$, then the row sum $S(n)$ satisfies the recurrence $S(n) = q(n) S(n-1)$. )

For example, with $f(n,k) = n-1$ and $g(n,k) = -1$, we have $$\sum_{k=0}^n (-1)^k \left[ n \atop k \right] = 0 , n \geq 2.$$

Are there any other known general conditions?

Answer by Mike Spivey for Maximum vertical distance for a lattice path when NSEW steps are allowed

2011-12-30T07:21:07Z

Anthony Quas's comments gave me the ideas I needed to answer the question. (Thanks, Anthony!) Here's the solution in case anyone else is interested. The answer turns out to be that the number of $n$-step paths with max height $y$ is $\binom{2n}{n+y} + \binom{2n}{n+y+1}$.

First, let $(X_n,Y_n)$ denote the final position of an $n$-step NSEW lattice path starting at the origin. Let's count $N((X_n,Y_n) = (x,y))$. By switching to $(\pm 1, \pm 1)$ (i.e, NW, NE, SW, SE) steps, we make the transformation $(x,y) \to (x+y,y-x)$. The choices of $+1$s and $-1$s for the two coordinates are now independent. The number of ways to choose $n$ total $+1$s and $-1$s that add to $x+y$ is $\binom{n}{(n+x+y)/2)}$, and the other coordinate is similar. Thus $$N((X_n,Y_n) = (x,y)) = \binom{n}{(n+x+y)/2)} \binom{n}{(n+y-x)/2}.$$

Next, we find $N(Y_n = y)$ by summing over all possible values of $x$. Since only values of $x$ that make $(n+x+y)/2$ and $(n+y-x)/2$ integers are allowed, thanks to Vandermonde's convolution we get $$N(Y_n = y) = \binom{2n}{n+y}.$$

Finally, let $M_n = \max_{0 \leq i \leq n} \{Y_i\}$. My question is asking for the value of $N(M_n = y)$. We have $N(M_n \geq y, Y_n = b)$ equal to $N(Y_n = b)$, if $b \geq y$; and, by the reflection principle (across the horizontal line of height $y$) equal to $N(Y_n = 2y-b)$, if $b < y$. Thus $$N(M_n \geq y) = \sum_{b \geq y} N(Y_n = b) + \sum_{b \leq y-1} N(Y_n = 2y-b)$$ $$= \sum_{b \geq y} N(Y_n = b) + \sum_{b \geq y+1} N(Y_n = b)$$ $$= N(Y_n = y) + 2 N(Y_n \geq y+1).$$ Therefore, $$N(M_n = y) = N(M_n \geq y) - N(M_n \geq y+1) = N(Y_n = y) + N(Y_n = y+1),$$ or $$N(M_n = y) = \binom{2n}{n+y} + \binom{2n}{n+y+1}.$$

When does symmetry in an optimization problem imply that all variables are equal at optimality?

2011-03-17T04:51:07Z

There are many optimization problems in which the variables are symmetric in the objective and the constraints; i.e., you can swap any two variables, and the problem remains the same. Let's call such problems symmetric optimization problems. The optimal solution for a symmetric optimization problem - like many of the ones that show up in calculus texts - frequently has all variables equal. To take some simple examples,

The rectangle with fixed area that minimizes perimeter is a square. (Minimize $2x+2y$ subject to $xy = A$ and $x,y \geq 0$.)
The rectangle with fixed perimeter that maximizes area is a square. (Maximize $xy$ subject to $2x + 2y = P$ and $x,y \geq 0$.)
The difference between the arithmetic mean and the geometric mean of a set of numbers is minimized (and equals $0$) when all the numbers are equal.

There are also more complicated symmetric optimization problems for which the variables are equal at optimality, such as the one in this recent math.SE question.

However, it is not true that every symmetric optimization problem has all variables equal at optimality. For example, the problem of minimizing $x +y$ subject to $x^2 + y^2 \geq 1$ and $x, y \geq 0$ has $(0,1)$ and $(1,0)$ as the optimal solutions.

Does anyone know of general conditions on a symmetric optimization problem that guarantee the optimal solution has all variables equal?

The existence of such conditions might be very nice. Unless the conditions themselves are ugly, they ought to vastly simplify solving a large class of symmetric optimization problems.

(Maybe convexity plays a role? My last example has a nonconvex feasible region.)

Solving a general two-term combinatorial recurrence relation

2010-10-06T15:48:00Z

What is known about explicit (not necessarily closed-form) solutions to the recurrence $$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$ with initial condition $R_0^0 = 1$ and with $R^n_k = 0$ for $n < 0$ or $k < 0$? Special cases of this are closely related to recurrences satisfied by some interesting combinatorial numbers, such as the binomial coefficients and the Stirling numbers.

The more general recurrence $$R^n_k= (\alpha n + \beta k + \gamma) R^{n-1}_k + (\alpha' n + \beta' k + \gamma') R^{n-1} _{k-1},$$

is open Problem 6.94 in Concrete Mathematics (2nd edition, p. 319).

The closest published result I have found thus far is the following formula due to Neuwirth ("Recursively defined combinatorial functions: Extending Galton's board," Discrete Mathematics, 2001) for the case $\alpha' = 0$ of the Concrete Mathematics problem,

$$R^n_k = \prod_{i=1}^k (\beta' i + \gamma') \sum_{i=0}^n \sum_{j=0}^n s^n_i \binom{i}{j} S^j_k \alpha^{n-i} (\gamma - \alpha)^{i-j} \beta^{j-k},$$

which, of course, gives me an answer to my question when $\alpha'=0$. (Here, $s^n_i$ and $S^j_k$ are unsigned Stirling numbers of the first and second kinds, respectively.)

I have tried generating functions without any success thus far. An answer like Neuwirth's that involves sums and binomial coefficients or Stirling numbers would be fine, as would a partial answer or just another idea to try.

Can this nested sum be expressed in terms of generalized harmonic numbers and the cycle index polynomials of the symmetric groups?

2010-12-23T19:37:46Z

For a paper I was working on recently I needed to find the value of the following sum:

$$S(n,k) = \sum_{i_1 = 1}^n \sum_{i_2 = i_1+1}^n \cdots \sum_{i_k=i_{k-1}+1}^n \frac{1}{i_1 i_2 \cdots i_k}.$$

I found a couple of references (by Adamchik and Cheon and El-Mikkaway) that have an expression for $S(n,k)$ as a polynomial containing generalized harmonic numbers $H_n^{(r)}$, where $$H_n^{(r)} = \sum_{j=1}^n \frac{1}{j^r}.$$ For example, $$S(n,2) = \frac{1}{2}\left(H_n^2 - H^{(2)}_n \right),$$ $$S(n,3) = \frac{1}{6}\left(H_n^3 - 3H_n H^{(2)}_n + 2 H_n^{(3)}\right),$$ $$S(n,4) = \frac{1}{24}\left(H_n^4 - 6 H^2_n H_n^{(2)} + 3 (H_n^{(2)})^2 + 8 H_n H_n^{(3)} - 6 H_n^{(4)}\right).$$

Neither of these papers considers the corresponding polynomial sequence of indeterminates (the polynomials before substituting in the generalized harmonic numbers), though. Calculations for small values of $n$ indicate that these are the cycle index polynomials of the symmetric groups, with the sign pattern such that each factor of $H_n^{(r)}$ contributes a $+1$ if $r$ is odd and a $-1$ if $r$ is even.

Could someone give a proof of this, particularly one with a combinatorial flavor that gives some real insight into why the cycle index polynomials of the symmetric groups show up here (assuming that they do)?

(For the record, I don't need this answered for my paper. I just want to know for my own sake.)

As a side note, the papers also give the extremely (and, to me, surprisingly) simple expression $$S(n,k) = \frac{1}{n!} \left[ n+1 \atop k+1 \right],$$ where $\left[ n \atop k \right]$ is an unsigned Stirling number of the first kind.

Answer by Mike Spivey for Binomial coefficient in Andrews' partition book

2011-10-19T20:17:02Z

This also follows from the Chu-Vandermonde identity ${s+t \choose n}=\sum_{k=0}^n {s \choose k}{t \choose n-k}$ and the upper negation rule for binomial coefficients $\binom{r}{k} = (-1)^k \binom{k-r-1}{k}$.

$$\sum_{\substack{i+j=s \atop i\geq 0, j \geq 0}}\binom{A-n+j}{j}\binom{n-j}{i} = \sum_{j=0}^s \binom{A-n+j}{j}\binom{n-j}{s-j}.$$ Then apply upper negation to get $$\sum_{j=0}^s (-1)^j \binom{-A+n-1}{j} (-1)^{s-j}\binom{s-n-1}{s-j}. $$ Chu-Vandermonde followed by upper negation again yields $$= (-1)^s \binom{-A+s-2}{s} = \binom{A+1}{s}.$$

Answer by Mike Spivey for Random Sampling a linearly constrained region in n-dimensions...

2011-09-24T03:07:26Z

Your constraints $x_n \geq 0$, $\sum_{n=1}^N x_n = 1$, are those for the standard simplex. You could try uniform sampling from the standard simplex, and then reject any sample that doesn't also satisfy the $x_n \leq c_n$ constraints.

An alternative to the procedure described in the linked paper above for uniform sampling from the standard simplex is to generate $n$ exponential(1) random variables $X_1, X_2, \ldots, X_n$ and let $Y_i = X_i/\sum_{i=1}^n X_i$. Then $(Y_1,Y_2,\ldots,Y_n)$ is uniformly distributed on the standard simplex. This can be thought of as generating a random vector from the symmetric Dirichlet distribution. (Also, generating exponential(1) random variables is easy; if $Z \sim U(0,1)$ then $-\ln(Z)$ has an exponential(1) distribution.) Once again, you would then reject any sample that doesn't also satisfy the $x_n \leq c_n$ constraints.

Answer by Mike Spivey for Identifying poisoned wines

2011-06-08T04:11:54Z

This problem also goes by the name "nonadaptive combinatorial group testing" and has been around since at least World War II, when the U.S. government was trying to isolate syphilis cases in soldiers. ("Nonadaptive" means you have to specify all the tests in advance, whereas "adaptive" means you can use the results from previous tests before deciding which ones to do next.)

The standard reference on group testing appears to be Combinatorial Group Testing and Its Applications, by Du and Hwang. Part II, which comprises Chapters 7-9, is on nonadaptive testing. In particular, finding optimal testing structures when there are two or more "defectives" is still an open problem.

However, if $t(d,n)$ is the number of tests required to isolate $d$ defectives out of $n$ total subjects, the bounds $\Omega(\frac{d^2}{\log d} \log n) \leq t(d,n) \leq O(d^2 \log n)$ are known. The Wikipedia article on disjunct matrices has a discussion and some proofs.

It might be interesting to compare the solution for the adaptive version of this problem, as we can give a definite answer in this case.

Let $n(t)$ denote the maximum number of bottles of wine for which 2 poisoned ones can be identified in $t$ adaptive tests. In "Group testing with two and three defectives" (Annals of the New York Academy of Sciences 576, pp. 86-96, 1989) Chang, Hwang, and Weng give explicit testing procedures that yield the lower bounds $$n(t) \geq 89 \cdot 2^{\frac{t}{2}-6}, t \text{ even, } t \geq 12;$$ $$n(t) \geq 63 \cdot 2^{\frac{t-1}{2}-5}, t \text{ odd, } t \geq 13.$$

In the Du and Hwang text it is shown that, for $t \geq 4$, we have the upper bound $$n(t) \leq 2^{\frac{t+1}{2}} - 1/2.$$
(Note that this is the upper bound on $f(n)$ given in Sergey Norin's answer.)

These bounds tell us that $n(18) \leq 723$ but that $n(19) \geq 1008$. Thus 2 poisoned bottles can be identified out of 1000 in 19 adaptive tests but no fewer, using the testing procedure described in the Chang, Hwang, and Weng paper.

Answer by Mike Spivey for Multiplicative Convolution for Binomial Coefficients

2011-04-15T00:55:10Z

Riordan and Stein, in "Arrangements on Chessboards" (Journal of Combinatorial Theory, Series A, 12 72-80, 1972) consider the numbers $A(r,s,k)$ defined by $$\sum_{r,s} \binom{n}{r} \binom{m}{s} A(r,s,k) = \binom{nm}{k},$$ or, as others have pointed out, the number of $r \times s$ $(0,1)$-matrices with $k$ $1$'s and with at least one $1$ in every row and every column. They obtain two formulas for these numbers:

$$A(r,s,k) = \sum_{i,j} (-1)^{i+j+r+s} \binom{r}{i} \binom{s}{j} \binom{ij}{k},$$

$$A(r,s,k) = \sum_n \frac{r! s!}{k!} S(n,r) S(n,s) s(k,n),$$ where $S(n,r)$ and $s(k,n)$ are Stirling numbers of the second and first kinds, respectively.

They also obtain the recurrence relation $$(k+1)A(r,s,k+1) +k A(r,s,k) $$ $$= rs \left(A(r,s,k) + A(r-1,s,k) + A(r,s-1,k) + A(r-1,s-1,k)\right)$$ and that $A(r,s,k)$ is the coefficient of $t^k$ in $$\sum_j (-1)^{s+j} \binom{s}{j} \left( (1+t)^j-1) \right)^r,$$ as in Richard Stanley's answer.

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-14T05:56:06Z

I asked this question at math.SE a couple of months ago and only got a partial answer, so I thought I would try here.

It is known that, for $n \geq 5$, it is possible to partition the integers $\{1, 2, \ldots, n\}$ into two disjoint subsets such that the product of the elements in one set equals the sum of the elements in the other. One solution is the following:

Let $N = \{1, 2, \ldots, n\}$.

If $n$ is even, take $P = \{1, \frac{n-2}{2}, n\}$ and $N-P$ as the two sets.

If $n$ is odd, take $P = \{1, \frac{n-1}{2}, n-1\}$ and $N-P$ as the two sets.

My question is this:

Is this partition unique for infinitely many $n$?

Background: The problem of proving that the partition is possible was posed several years ago as Problem 2826 in the journal Crux Mathematicorum, with solutions in the April 2004 issue. Every one of the 20 or so solvers (including me, which is why I'm interested in the question) came up with the partition given here. The person who originally posed the problem also asked if the partition is unique for infinitely many $n$. I don't think anyone ever submitted an answer to that latter question to Crux (although I cannot verify that, as I no longer have a subscription). I thought someone here might be able to give an answer.

The partial answers to the math.SE question were

1) Matthew Conroy showed by brute force calculation that, for $5 \leq n \leq 100$, the only values of $n$ that have only this solution are $5,6,7,8,9,13,18,$ and $34$.

2) Derek Jennings showed that for $n=4m$ we can obtain a partition with the required property by taking $P=\{8,m−1,m+1\}$ for $m>1$ and $m \neq 7$ or $9$. Thus the partition in the question is not unique for $n$ a multiple of $4$ and greater than $36$.

Asymptotic difference between a function and its "binomial average"

2010-11-20T21:46:18Z

(I posted this question on Math.SE a few weeks ago. I got a few comments, but nothing definite, and so I thought I would try MO.)

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number.

Dividing by $2^n$, we have $$2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = H_n - \sum_{k=1}^n \frac{1}{k 2^k}.$$

The sum on the left can now be interpreted as a weighted average of the harmonic numbers through $H_n$ - where the weights, of course, are the binomial coefficients. Thus the difference between $H_n$ and its "binomial average" (I'm guessing there's no term for this) is $$H_n - 2^{-n} \sum_{k=0}^n \binom{n}{k} H_k = \sum_{k=1}^n \frac{1}{k 2^k}.$$

The sum on the right is known to converge to $\ln 2$ as $n \to \infty$. (Substitute $-\frac{1}{2}$ into the Maclaurin series for $\ln (1+x)$.)

This leads me to my question:

Can we classify nonnegative functions $f(n)$ for which $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right)$$ is finite and nonzero?

It would seem that if $f$ increases sufficiently rapidly, then the limit would be $\infty$. This is the case with both $f(n) = a^n$ and $f(n) = n$. If $f$ decreases or is constant, then the limit is zero. If $f$ has basically logarithmic growth, then it seems the limit would behave as $H_n$. But can this be proved? And what about other sublinear, increasing functions?

The two Math.SE responses were

"I agree that logarithmic growth is what you need. The 'binomial average' of $f(n)$ should be about $f(n/2)$." (from Michael Lugo)
A reformulation of the problem in terms of exponential generating functions. (from Qiaochu Yuan)

Answer by Mike Spivey for Asymptotic difference between a function and its "binomial average"

2011-02-17T23:17:33Z

The function $f(n)$ must be $\Theta (\log n)$. Update: As Didier Piau points out in the comments, we can say something stronger: $\frac{f(n)}{\log_2 n} \to L$ as $n \to \infty$. See the update at the end of the argument.

Suppose, for some positive $L$ (the negative case is similar), $$\lim_{n \to \infty} \left(f(n) - 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k) \right) = L.$$ Thus $$f(n) = L + r(n) + 2^{-n} \sum_{k=0}^n \binom{n}{k} f(k)$$ for some function $r(n)$ such that $r(n) \to 0$ as $n \to \infty$. This gives us a recurrence relation for $f(n)$. Since $r(n) \to 0$, $L + r(n) > 0$ for all sufficiently large $n$. So, for all sufficiently large $n$, there exist positive constants $C$ and $D$ such that $C < L + r(n) < D$. Since the initial terms in the function eventually become negligible in determining the value of $f(n)$ via the recurrence relation, there exist functions $g(n)$ and $h(n)$ such that for all sufficiently large $n$, $g(n) \leq f(n) \leq h(n)$ and $g(n)$ and $h(n)$ satisfy $$g(n) = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} g(k),$$ $$h(n) = D + 2^{-n} \sum_{k=0}^n \binom{n}{k} h(k).$$

So the problem reduces to showing that $g(n)$ and $h(n)$ are $\Theta (\log n)$. The argument is the same for both.

There are some different ways to do this; my favorite is to interpret the $g(n)$ recurrence probabilistically. Suppose we start at time $g(0)$, we flip a set of $n$ coins simultaneously each round, and it takes $C$ time units to do one round of flips. When a coin turns up heads for the first time, we cease flipping it. Let $T(n)$ be the time at which the last coin to achieve its first head does so. To find $E[T(n)]$, condition on the number of coins that achieve heads in the first round of flips. This yields $$E[T(n)] = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} E[T(n-k)] = C + 2^{-n} \sum_{k=0}^n \binom{n}{k} E[T(k)].$$ Thus $g(n) = E[T(n)]$.

Another way to view $T(n)$ is that it is $g(0) + C M_n$, where $M_n = \max\{X_1, X_2, \ldots, X_n\}$ and the $X_i$'s are independent and identically distributed geometric $(1/2)$ random variables. (Each geometric random variable models the first time a head appears.) Thus $g(n) = g(0) + C E[M_n]$. It is known that $\frac{H_n}{\log 2} \leq E[M_n] \leq \frac{H_n}{\log 2} + 1$ and, more precisely, that $E[M_n]$ is logarithmically summable to $\frac{H_n}{\log 2} + \frac{1}{2}$. (See, for example, Bennett Eisenberg's paper "On the expectation of the maximum of IID geometric random variables," Statistics and Probability Letters 78 (2008) 135-143. See also this MO question, "What is the Expected Maximum out of a Sample (size $n$) from a Geometric Distribution?")

Thus $g(n) = \frac{C}{\log 2} \log n + O(1)$, which means that $h(n) = \frac{D}{\log 2} \log n + O(1)$ and $f(n) = \Theta (\log n)$.

Update: Given $\epsilon > 0$, if we take take $C > 0$ such that $L - \epsilon \leq C < L$ and $D = L + \epsilon$, this argument shows that $$L - \epsilon + O\left(\frac{1}{\log n}\right) \leq \frac{f(n)}{\log_2 n} \leq L + \epsilon + O\left(\frac{1}{\log n}\right).$$

Thus, as $n \to \infty$, $\frac{f(n)}{\log_2 n} \to L.$

For some other ideas that pertain to this result, including what are effectively some alternative derivations, see Pradipta's recent MO question, "Coin Flipping and a Recurrence Relation". In fact, reading Pradipta's question and some of its answers gave me the ideas needed to construct this argument! So, thanks go to Pradipta, Didier Piau, Emil Jeřábek, and Louigi Addario-Berry.

Answer by Mike Spivey for Coin flipping and a recurrence relation

2011-02-16T21:42:54Z

This is exactly the problem of finding the expected maximum of $n$ iid geometric (1/2) random variables. This is because the geometric distribution models the time until the first success in independent Bernoulli trials, and each coin flip can be considered an independent Bernoulli trial.

The question of finding the expected maximum of $n$ iid geometric random variables was asked a few months ago on MO. You can see from the accepted answer there that the expected value can be expressed as

$$\sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \frac{1}{1-\frac{1}{2^i}},$$
which is the last expression in Didier Piau's answer in a slightly different form.

The other answer cites a paper by Bennett Eisenberg that claims that "There is no... simple expression for... the expected value of the maximum of $n$ IID geometric random variables." However, the paper itself proves that $E[T(n)] - \sum_{k=1}^n \frac{1}{\lambda k}$ "is very close to 1/2 not only for moderate values of $\lambda$, but also for relatively small values of $n$ and that this difference is logarithmically summable to 1/2 for all values of $\lambda$." In your case, $\lambda = \ln 2$. Thus $E[T(n)]$ is very close to $\frac{H_n}{\ln 2} + \frac{1}{2}$, right in the middle of the range given by Louigi Addario-Berry's answer.

Answer by Mike Spivey for Extending arithmetic functions to groups

2011-02-11T05:06:20Z

It looks like some of these ideas appear in Philip Hall's paper, "The Eulerian functions of a group," Quart. J. Math. Oxford Ser. 134-151, 1936. He discusses both an Euler $\phi$ function and a Möbius function defined on groups.

The Möbius function is as Tom Leinster describes in his answer to Q1.

The function $\phi_n(G)$ is the total number of distinct $n$-bases of the group $G$, where an $n$-basis is any ordered set of $n$ elements of $G$ which generate $G$. Thus, if $G$ is cyclic of order $m$, $\phi_1(G)$ is the usual Euler function $\phi(m)$.

Answer by Mike Spivey for Expected second moment for random points on a circle

2011-01-19T21:08:12Z

The problem is equivalent to choosing $n-1$ points at random on the unit interval and considering the length of the longest resulting subinterval. Given that, the distribution of the maximum and its expected value are in my answer to this recent math.SE question on Average Length of the Longest Segment. It's closely related to the one given in the comments above by Shai Covo. I'll reproduce the answer here (which is given in terms of making $n-1$ cuts randomly chosen on a rope of unit length).

If $X_1, X_2, \ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the resulting pieces of rope.

The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, \ldots, c_k$, respectively (where $\sum_{i=1}^k c_i \leq 1$), is $$(1-c_1-c_2-\ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, \ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - \ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.

If $V_{(n)}$ denotes the largest piece of rope, then $$P(V_{(n)} > x) = P(V_1 > x \text{ or } V_2 > x \text{ or } \cdots \text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above, $$P(V_{(n)} > x) = n(1-x)^{n-1} - \binom{n}{2} (1 - 2x)^{n-1} + \cdots $$ $$+ (-1)^{k-1} \binom{n}{k} (1 - kx)^{n-1} + \cdots,$$ where the sum continues until $kx > 1$.

Therefore, $$E[V_{(n)}] = \int_0^{\infty} P(V_{(n)} > x) dx = \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \int_0^{1/k} (1 - kx)^{n-1} dx $$ $$= \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{1}{nk} = \frac{1}{n} \sum_{k=1}^n \frac{\binom{n}{k}}{k} (-1)^{k-1} = \frac{H_n}{n},$$ where the last step applies a known binomial sum identity.

For much more on this problem, see Section 6.4 ("Random Division of an Interval") in David and Nagaraja's Order Statistics, pages 133-137, and the corresponding exercises on pages 153-155.

As a side note, the distribution of $V_{(n)}$ was apparently first obtained by Ronald Fisher in "Tests of Significance in Harmonic Analysis," Proceedings of the Royal Society of London, Series A, 1929, pp 54-59. (Sorry for the JSTOR link.)

Answer by Mike Spivey for Summation of a series of floor functions

2010-12-07T03:45:30Z

The following reduces the number of terms that you are adding up, from about $(x-1)N$ to about $N(1-1/x)$ (i.e, by a factor of $x$). So it should speed up your calculations some. Unfortunately, the number of terms is still $O(N)$, and so it won't reduce the asymptotic run time, but maybe it will still be useful.

$$\sum_{k=N}^{xN} \left\lfloor \frac{N^2}{k} \right\rfloor = \sum_{k=\lfloor N/x \rfloor +1}^N \left\lfloor \frac{N^2}{k} \right\rfloor + N - xN \left\{ \frac{N}{x}\right\},$$ where $\{y\}$ denotes the fractional part of $y$.

This is an application of the following "fun" result I published with Natalio Guersenzvaig a few years ago: $$\sum_{d=j+1}^{k} \lfloor n/d \rfloor - \sum_{d= \lfloor n/k \rfloor + 1}^{\lfloor n/j \rfloor} \lfloor n/d \rfloor = k \lfloor n/k \rfloor - j \lfloor n/j \rfloor.$$ (This is Corollary 4 in "Some Inversion Formulas for Sums of Quotients," Crux Mathematicorum, 32 (1): 39-43, 2006.)

Answer by Mike Spivey for More open problems

2010-12-04T20:19:15Z

I have found Richard Guy's Unsolved Problems in Number Theory to be very interesting and useful.

Springer also publishes Unsolved Problems in Geometry (by Croft, Falconer, and Guy).

Answer by Mike Spivey for Does War have infinite expected length?

2010-10-01T17:22:45Z

My paper "Cycles in War" addresses this question, too. I was interested in characterizing the kinds of cycles that can occur. In other words, what does the structure of a cycle in War actually look like? I simplified the problem by assuming that wars are not possible (i.e., the cards have a strict ranking from 1 to n, where n is the number of cards in the deck). Even in this simpler version I found it difficult to characterize all of the cycles. However, in the case that the winning card goes to the bottom of the winning player's deck before the losing card, I was able to find a way to construct a deal of an $n$-card deck that cycles, for any $n$ that is not a power of 2 or three times a power of 2.

For example, the following deal of a 52-card deck cycles.


26 46  1  7  8 27  9 28 29 47  2 10 11 30 12 31 32 48  3 13 14 33 15 34 35 49

16 36 17 37 38 50  4 18 19 39 20 40 41 51  5 21 22 42 23 43 44 52  6 24 25 45

It takes over 30,000 battles for the deck to return to this ordering. The mathematical argument for why this deal cycles is in the paper~~, which has been accepted for publication by the journal Integers but has not appeared in print yet~~. Among other things, the re-loading rules do make a difference, as other people have already noted here. Also, given that characterizing cycle structures when wars are not possible turns out to be difficult (or, at least, I found it so), one should expect that characterizing cycles in the standard version of the game in which wars are possible would be even more difficult.

Edit: The paper has now been published on the Integers web site, in the games section, as Vol. 10, Article G2, 2010, pp. 747-764.

How does a tournament's structure affect the likelihood that the best player will win?

2010-10-17T06:02:35Z

Background

The origin of this question is a conversation I had with some friends a few years ago. At the time, Roger Federer and Tiger Woods were dominating professional tennis and golf, respectively, and we were comparing and contrasting the two. It occurred to me that there was a mathematical question that was relevant to our discussion; namely, the structure of golf tournaments vs. tennis tournaments.

For example, the Masters is a four-round tournament. After two rounds, roughly the bottom half of the field is sent home. The winner is the person with the lowest total score after four rounds. On the other hand, Wimbledon is a single-elimination tournament; the winner must defeat seven other players in head-to-head competition. From a structural standpoint, if you are the best player in the field, is it harder to win a tournament like the Master's or harder to win a tournament like Wimbledon?

The mathematics

More generally, how does a tournament's structure affect the likelihood that the best player will win?

This question is a bit fuzzy because there are some modeling issues involved that will affect the answer. Something like the following seems a reasonable place to start.

Let $F_1, F_2, \ldots F_n$ be independent normal distributions such that a random variable drawn from distribution $F_i$ gives the performance by the $i$th best player in a particular round of competition. So we would have $\mu_{F_i} > \mu_{F_j}$ when $i < j$. Assuming that the $F_i$'s have the same variance seems a reasonable starting point, too, as does the assumption that a given player's performances from round to round are independent.

First question: What is the best way to model the $\mu_{F_i}$'s vs. the $\sigma_{F_i}$'s? The difference $\mu_{F_1} - \mu_{F_2}$ ought to be much larger than $\mu_{F_{99}} - \mu_{F_{100}}$, so maybe something like $\mu_{F_i} = 1/i$ would work, but I'm not sure what makes for a reasonable variance to go with this function.

For specificity's sake, let's assume three types of tournament structure: 1) that of the Masters, 2) that of Wimbledon, and 3) that of the World Cup (which has a round-robin stage before moving to a single-elimination stage).

Second question: Given a satisfactory answer to the first question, what is the probability that Player 1 will win each of these three tournaments?

My reasoning so far

It seems to me that the two most important factors involved that would prevent the best player from winning the tournament are

an unusually poor performance from the best player in a particular round, and
an unusually good performance from someone else in the field in a particular round.

There's not much that the tournament's structure could do to mitigate factor (1), although a single-elimination tournament would seem to be the most unforgiving. On the other hand, the structure of the tournament probably has a large effect on the impact of factor (2). For instance, an incredible performance from someone in two separate rounds of the Masters raises the bar quite a bit for the best player. On the other hand, in a tournament like Wimbledon two great performances might lead to two upsets of major players but doesn't provide any advantage in later rounds, and, for the best player to be negatively affected, he/she would have to be playing directly against the overperforming player. Also, if there are enough players around (like the early rounds of Wimbledon and all the way through the Masters) there is a high probability that someone in the field will turn in two great performances in two different rounds.

So, if you are the best player in the field it seems to me that contests in which you are essentially playing most of the field simultaneously, like the Masters, would be more difficult to win than single-elimination tournaments like Wimbledon, which in turn would be more difficult to win than those with a round-robin format in the early rounds and single-elimination in the later rounds, like the World Cup.

Third question: Are there any known results that address this problem of the effect of tournament structure on the best player's chances of winning?

I would be happy to see critiques/comments on my modeling and my reasoning as well.

Answer by Mike Spivey for How does a tournament's structure affect the likelihood that the best player will win?

2010-11-23T06:34:52Z

It turns out this problem has been studied extensively in the economics literature. The motivation is to create some sort of competition that will maximize the likelihood of the best candidate for a job or the best application for a grant actually being awarded the job or grant.

For example, "The Predictive Power of Noisy Elimination Tournaments," by Dmitry Ryvkin, examines the effects of seeding under different numbers of players and some different performance probability distributions.

The paper "Three Prominent Tournament Formats: Predictive Power and Costs," (apparently published in Management Science under the title "The Predictive Power of Three Prominent Tournament Formats"), by Ryvkin and Andreas Ortmann, addresses my question exactly, though. They calculate the exact probability (under uniform, normal, and Pareto distributions for player performance) that the best player wins a round robin tournament, a binary elimination tournament, and a contest. (The last involves all players performing simultaneously at once; the winner is the player with the best performance.) By calculating these probabilities for specific values they show numerically that for all but small numbers of players in a tournament, the best player in the tournament has a higher probability of winning a round robin tournament than a binary elimination tournament and a higher probability of winning a binary elimination tournament than a contest.

Given these results, it does appear that (all other things being equal) the structure of golf tournaments makes them more difficult to win than tennis tournaments, and, consequently, that dominating professional golf is even more impressive than dominating professional tennis.

Answer by Mike Spivey for Least square given constraint on subcomponents

2010-11-23T02:07:29Z

You can express this problem as a quadratically constrained quadratic program (QCQP). Unfortunately, because of the equality constraint, the QCQP will be nonconvex. However, there is some discussion on the Wikipedia page for handling nonconvex QCQP's, and a Google search should turn up more. This paper "Relaxations and Randomized Methods for Nonconvex QCQP's" might help, too; Example 1.2.1 in the paper is very similar to your problem.

Answer by Mike Spivey for What recent discoveries have amateur mathematicians made?

2010-11-20T19:00:22Z

Bill Gates co-authored the following paper in the 1970s with Christos Papadimitriou:

"Bounds for sorting by prefix reversal," Discrete Mathematics 27 (1979), no. 1, 47–57, MR0534952.

Not sure if Gates counts as an amateur, but he is at least a college dropout. :)

The only reason I know this is because once I ran across a book or article that discusses the results in this paper and then says something like, "Yes, this is THE Bill Gates." I was almost certain the book or article was by Knuth, but now I can't find the reference in any of my Knuth books. If someone else knows the reference I'm talking about, I would be grateful if they would post it as a comment to my answer. (It now bothers me that I can't find that reference. :) )

Laplace's summation formula

2010-10-24T03:22:58Z

I recently came across the following formula, which is apparently known as Laplace's summation formula:

$$\int_a^b f(x) dx = \sum_{k=a}^{b-1} f(k) + \frac{1}{2} \left(f(b) - f(a)\right) - \frac{1}{12} \left(\Delta f(b) - \Delta f(a)\right) $$ $$+ \frac{1}{24} \left( \Delta^2 f(b) - \Delta^2 f(a) \right) - \frac{19}{720} \left(\Delta^3 f(b) - \Delta^3 f(a) \right) + \cdots$$

(Of course, the right-hand side isn't guaranteed to converge.) The coefficient on the term with $\Delta^{k-1}$ is $\frac{c_k}{k!}$, where $c_k$ is apparently called either a Cauchy number of the first kind or a Bernoulli number of the second kind.

The formula looks to me like a finite calculus version of the Euler-Maclaurin summation formula.

I'm trying to find out more about Laplace's summation formula. However, the usual suspects (the arXiv, Wikipedia, MathWorld, Google) aren't turning up much. There was a little on MathSciNet, the most promising of which was a paper by Merlini, Sprugnoli, and Verri entitled "The Cauchy Numbers" (Discrete Mathematics 306(16): 1906-1920, 2006). The MathSciNet review says, "Application of the Laplace summation formula involving the harmonic numbers [is] also given." I've requested the paper through interlibrary loan, but it has not arrived yet.

While I'm interested in the formula in general, I'm particularly interested in these two questions.

What applications are there for the Laplace summation formula? (It seems like there ought to be a sufficient number of applications for it to deserve having Laplace's name attached to it. I suppose one could use it for asymptotic analysis, but I'm not sure what the advantage would be over Euler-Maclaurin.)
What is the error bound on the formula when it is truncated after $n$ terms?

I wasn't sure how to tag this; feel free to retag.

Answer by Mike Spivey for Nontrivial question about fibonacci numbers?

2010-11-19T18:03:24Z

Two answers:

Thomas Koshy's near-encyclopedic text Fibonacci and Lucas Numbers with Applications contains many, many results on Fibonacci numbers, many of which can be proved using techniques available to undergraduates.
As a variant on gowers' answer about taking powers of the matrix

    1 1
    1 0

I wrote a paper a few years ago on using the determinant sum property and this matrix to prove some Fibonacci identities. It appeared in The College Mathematics Journal and is very much at the undergraduate level.

Answer by Mike Spivey for Can assignment solve stable marriage?

2010-11-14T06:43:28Z

A related question is "Can linear programming solve stable marriage?" John H. Vande Vate proved in 1989 ("Linear programming brings marital bliss") that the answer is "Yes." He found a set of linear inequalities whose extreme points are precisely the stable marriages. His results were both generalized and simplified by Uriel Rothblum three years later ("Characterization of stable matchings as extreme points of a polytope"). Rothblum's characterization uses the standard assignment problem constraints and some additional constraints that rule out the unstable marriages. This isn't quite what you're asking for, but it is related and so I thought you might be interested.

Answer by Mike Spivey for What topics should be included in a calculus-for-the-liberal arts course?

2010-11-10T21:47:24Z

Several years ago the liberal-arts-ish university where I was at the time was pushing to have more interaction between the sciences and the humanities. In that spirit I volunteered to give an hour-long seminar entitled, "So You Think You're Educated, But You Don't Know Calculus: A Brief Introduction to One of Humanity's Greatest Inventions." It was aimed at the humanities faculty. My goal was to explain the big ideas behind calculus and place them in their historical and philosophical context for an audience of very smart people with weak math backgrounds. You might be able to use the historical and philosophical context part of the talk for the "ways in which differential and integral calculus have played a role in the history of science" aspect of your question. You are welcome to borrow freely from my presentation.

In retrospect the title may have been a bit too audacious, but the talk went much better than I had expected. A few of the scientists showed up for fun, but most of the audience were folks from the humanities and social sciences. They were engaged, and they peppered me with questions for half an hour after the talk was over. After I left there were still people who stayed behind to discuss the seminar. Later I even got an email from the provost (a religion scholar) who wanted me to meet with him to discuss the ideas in the talk! It was, frankly, the most successful academic talk I've ever given - and much more so than the one I gave three days ago at a math conference that was attended by eight people in a room that could hold hundreds and yielded no questions. :(

One caveat: When I discuss the philosophical implications of calculus, I'm doing so as I think they appeared to people at the time, not today. Clearly, humanity's consensus on these big questions has changed in the last 300 years.

The other thing I would say is to second Deane Yang's recommendation to look at the Hughes-Hallet, et al, calculus texts. I know there are strong opinions on the calculus reform movement, and I don't want to wade into that. But what the Hughes-Hallet texts do well (in my opinion) is to emphasize ideas and mathematical thinking over rote computation. Since you're after the former, looking at what they've done may be helpful.

Answer by Mike Spivey for Some questions about Invexity

2010-10-27T05:37:27Z

There are a lot of generalizations or variations of convexity, such as quasi-convexity, pseudo-convexity, semilocal convexity, semilocal quasi-convexity, semilocal pseudo-convexity, strict versions of these, strong versions of these, etc. There is a reason for the existence of each term, in that each makes the hypotheses of some theorem tighter or has some other benefit (such as invexity making the KKT conditions not just necessary but sufficient). I agree with you that invexity ought to be better known, but it may have gotten lost in all the other generalizations/variations out there.

Comment by Mike Spivey

2012-01-29T05:10:51Z

@darij: I've added a reference to a note by Callan that gives the argument for the non-alternating version. It's more than three pages. :)

Comment by Mike Spivey

2011-12-29T21:17:07Z

@Anthony: Yes, I did mean it to be uniform. And that's a nice reformulation of the problem; thanks.

Comment by Mike Spivey

2011-12-01T23:24:15Z

+1 for the generating function formulation. As you say, the question is whether it is possible to simplify the expression for the constant term of the generating function.

Comment by Mike Spivey

2011-11-24T22:01:24Z

Look at the expression for $\left[ n \atop 3 \right]$ on the fifth line in Section 2 of Adamchik's paper. He does have $H_n^2$ there, not $H_n$.

Comment by Mike Spivey

2011-11-24T21:55:07Z

Also, the Migdal paper uses generating functions. I've tried those on my problem, and I haven't been able to make them work. (Maybe someone else can, of course.) But the point is that a reference to a slightly different problem in which someone uses a technique I've already tried doesn't solve my problem. If you can see how to make one of the techniques in one of the papers you mention solve my problem, though, please post the solution! I would upvote and accept such an answer.

Comment by Mike Spivey

2011-11-24T21:52:50Z

The recurrence relations in those papers don't have the parameters in the same form as in my question. As I said in my earlier comment, slight changes to the parameters in a partial difference equation can make a huge difference in the solution, so to answer my question I would need a reference in which the parameters are exactly of the same form.

Comment by Mike Spivey

2011-11-07T22:51:11Z

Unfortunately, the recurrences in those papers don't quite match up with the one I'm asking about. And with partial difference equations like these, slight changes in the parameters can make a huge difference in the solutions. Thank you for the interesting references, though.

Comment by Mike Spivey

2011-11-06T23:00:02Z

Another reference for this formula is Equation 8.21 of Charalambides's Enumerative Combinatorics (p. 291).

Comment by Mike Spivey

2011-10-31T04:18:04Z

@Leonid: My apologies for responding so late to your question; somehow I didn't get pinged by your use of "@Mike." All of the matrices in our paper are lower triangular, so the methods may not directly apply. However, one of the core ideas is that elementary and complete symmetric polynomials are inverse to each other, in some sense, and maybe you can adapt that idea to your situation. See, for example, p. 296 of Richard Stanley's Enumerative Combinatorics, Vol. II.

Comment by Mike Spivey

2011-09-05T20:48:28Z

@J.M.: No, although that paper pretty much says the same thing that the one I'm thinking of does. The reference I remember was longer ago than February 2010. Thanks anyway. :)

Comment by Mike Spivey

2011-06-27T19:57:18Z

@Igor: Full text is available via my web site here: math.pugetsound.edu/~mspivey/Symmetric.pdf.

Comment by Mike Spivey

2011-03-18T02:20:20Z

What François G. Dorais said. :) And thank you for taking the time to summarize the article so well.

Comment by Mike Spivey

2011-03-17T16:24:45Z

Thanks. So convexity is a sufficient condition.

Comment by Mike Spivey

2011-03-17T16:21:11Z

Thanks, Dirk; now I see what you mean. That's an interesting generalization.

Comment by Mike Spivey

2011-03-17T09:19:56Z

Dirk, your answer sounds interesting. Would you mind elaborating, for my sake? For instance, I don't think I could look at an optimization problem and recognize when your criterion applies. (My background is operations research, and my abstract algebra is unfortunately quite rusty.)