User fedja - MathOverflow

Answer by fedja for Rate of growth of an explicit integral

2013-05-24T21:23:43Z

David's approach is, indeed, superb. Here is an alternative proof with more analytic flavor. It gives a worse constant as presented here (I made next to no attempt to optimize it), but it shows a bit more and can also teach you a couple of useful techniques.

First, let's clear the ground a bit. The problem is equivalent to estimating the integral $$ \idotsint\limits_S \prod_{n=1}^N\left(\sum_{k=1}^n\frac{1}{\sqrt{x_{n-k+1}+\dots+x_n}}\right)dx_1\dots dx_N $$ where $S$ is the standard simplex $x_j\ge 0,\sum_j x_j\le 1$. I suspect that this is what you started with because your notation strongly suggests that your $1$ was actually $t_1$ initially, so I'll not dwell on this reformulation now and will go straight to the point.

The simplex is not a very nice body for integration, but, if we do not mind losing a factor of $4^N$, we can replace it by the cube $Q_N=[0,1/N]^N$ ($S$ can be covered by about $4^N$ cubes $\frac 1N(k_1,\dots k_N)+Q_N$ with $k_j\in\mathbb Z_+$, $\sum_j k_j\le N$. Clearly, the cube with $k_1=\dots=k_N=0$ gives the largest contribution. It is then natural to make the change of variable $x_j=y_j/N$ that makes the domain of integration the standard unit cube. The problem becomes to show that
$$ \idotsint\limits_Q \prod_{n=1}^N\left(\sum_{k=1}^n\frac{1}{\sqrt{y_{n-k+1}+\dots+y_n}}\right)dy_1\dots dy_N\le C^N N^{N/2} $$

Next, all those long sums under the square root are, probably, behaving essentially like $\sqrt k$ due to the law of large numbers, with only severe deviations possible for small $k$. Thus, it looks like we should be able to replace the sum $$ \sum_{k=1}^n\frac{1}{\sqrt{y_{n-k+1}+\dots+y_n}} $$ by $$ \left(\sum_{k=1}^n\frac 1{\sqrt k}\right)\max_{1\le k\le n} \sqrt{\frac k{ y_{n-k+1}+\dots+y_n }}\approx 2\sqrt k \max_{1\le k\le n}\sqrt{\frac k{ y_{n-k+1}+\dots+y_n }}.
$$ The factors $2\sqrt k$ multiply to just what we need. Thus, all that remains is to show that $$ \idotsint\limits_Q \prod_{n=1}^N\max_{1\le k\le n}\sqrt{\frac k{ y_{n-k+1}+\dots+y_n }} dy_1\dots dy_N\le C^N $$ If there were no maximum in $k$, just the product $\prod_{n=1}^N\sqrt{1/y_n}$, that would be a triviality. Moreover, we would have a lot of leeway in the possibility to replace the power $1/2$ by any other power less than $1$. We are going to use this leeway now and show that for every $p>1$, we have a pointwise estimate $$ \prod_{n=1}^N\max_{1\le k\le n}{\frac k{ y_{n-k+1}+\dots+y_n }}\le C(p)^N \left[\prod_{n=1}^N\frac{1}{y_n}\right]^p $$ This looks like the classical Hardy-Littlewood maximal function inequality in disguise, and, indeed, it is, though the maximal function one has to use here is the $\delta$-percentile one, which is rarely mentioned in the textbooks until you start dealing with the BMO spaces, so I'll remind the corresponding routines here.

Denote $z_n=\log(1/y_n)\ge 0$. Fix a small $\delta>0$. For each $n$, consider all intervals $I\subset[1,N]$ of integers containing $n$. Let $Z(I)$ be the least number such that at least $\delta|I|$ integers $m\in I$ satisfy $z_m\le Z(I)$ (we are really looking just for the "$\delta$-percentile" in the distribution of values on $I$, but due to the discrete setting instead of the continuous one, we have to handle things in a somewhat clumsy way). Put $Z_n=\max_{I:n\in I}Z(I)$.

Note now that $\frac k{ y_{n-k+1}+\dots+y_n }\le \delta^{-1}e^{Z_n}$ for every $k$, so the story will end if we demonstrate that our maximal operator $z\mapsto Z$ acts in $\ell^1$ with the norm at most $p$.

As usual, we play with the covering lemmas. Alas, Vitali, which is taught in every measure theory course, is not good enough for us because of the length tripling, so we'll use Besicovitch instead. Fortunately, in dimension 1, it is a piece of cake and reduces to the observation that is three intervals on the line contain a common point, then one of them is contained in the union of two others. Thus, we get the following

Lemma: From any finite collection of intervals on the line, one can choose a subcollection with the same union so that it covers no point more than twice.

(just remove the redundant intervals one by one using the observation above)

Now take any $t>0$ and consider the set $E=\{n:Z_n>t\}$. It is covered by intervals $I$ with $Z(I)>t$. Choosing a Besicovitch subcollection, we can assume that no point is covered more than twice. Let $F=\cup I$. Clearly, $|E|\le |F|$. On the other hand, the number of all indices $n\in F$ with $z_n\le t$ is at most $\delta\sum_I |I|\le 2\delta|F|$. Thus, the cardinality of the set $e=\{n:z_n>t\}$ is at least $(1-2\delta)|F|$. If $1-2\delta>p^{-1}$, we get $|E|\le p|e|$ for all $t$. Integrating this distributional inequality, we conclude that $$ \Vert Z\Vert_{\ell^1}\le p\Vert z\Vert_{\ell^1} $$ finishing the story.

As I said, this approach gives you a cruder bound, but it can often be used even when no nice algebraic identities are anywhere in sight.

I also could not help commenting on David's remark

so this shows that all your polynomials are polynomials in $\pi$. (I am feeling nicely superior to Mathematica now. )

IMHO, Mathematica never works when you really need it and has a strong tendency to irreversibly replace the gray cells in your brain when you don't really need it. I usually lament a lot about its complete impotence when one needs to determine whether some oscillatory integral is positive or negative, but its defendants always respond that numeric integration is not a purely algebraic problem. To see a human (albeit one with math. abilities well above average) beating it in its own field (exact symbolic computation of definite integrals involving simple radicals) gives me enormous satisfaction and some hope that not all is lost yet. :)

Moving one family of commuting self-adjoint operators to another without losing commutativity on the way

2011-01-06T21:39:22Z

This is actually not a question of mine, so I'll be short on motivation and say nothing beyond that if this were true, a few fancy harmonic analysis techniques that a colleague of mine used in proving his recent results could be replaced by the mean value theorem.

Suppose that $A_1,\dots,A_n$ and $B_1,\dots,B_n$ are two commuting families of self-adjoint operators in a Hilbert space $H$ (that is all $A$'s commute, all $B$'s commute, but $A$'s may not commute with $B$'s). Assume that $\|A_k-B_k\|\le 1$ for all $k$. Is it true that there exists a one-parameter family $C_k(t)$ of self-adjoint commuting (for each fixed $t$) operators such that $C_k(0)=A_k$, $C_k(1)=B_k$ and $\int_0^1\left\|\frac d{dt}C_k(t)\right\|dt\le M(n)$ where $M(n)$ is a constant depending on $n$ only? In other words, is the set of commuting $n$-tuples of self-adjoint operators a "chord-arc set"?

Two commuting mappings in the disk

2009-10-29T20:16:45Z

Suppose that $f$ and $g$ are two commuting continuous mappings from the closed unit disk (or, if you prefer, the closed unit ball in $R^n$) to itself. Does there always exist a point $x$ such that $f(x)=g(x)$?

If one of the mappings is invertible, then it is just a restatement of the Brower's fixed point theorem but I do not know the answer in the general case and would not even dare to guess what it must be. Also, the answer is well-known to be "Yes" in dimension $1$.

Answer by fedja for Is rigour just a ritual that most mathematicians wish to get rid of if they could?

2013-05-06T05:05:33Z

I guess the question "Is the rigor just a ritual" has got enough answers, so I'll address another one:

Has something happened in the world of mathematics that I am not aware of?

My answer is: yes, if you replace "aware of" by "consciously aware of". Of course, what I'll say will be "subjective and argumentative".

1) There are far too many people that call themselves "mathematicians" or "mathematical education specialists". Many of them are just street peddlers who make their living by selling their "results" and "theories" and whose mentality is that of an egg seller on the flea market. The goal is to get as good price as possible keeping the production costs as low as possible. One also has to maintain good relationships with nearby sellers and with market authorities and to keep an eye on the latest consumer trends. It would be nice to get a better place for the stand, etc. The question of the quality of eggs has to be addressed only if an angry mob of people is approaching. Otherwise, everything that is oval-shaped and white or brown in color will do.

2) The professor-student relationship is no longer that of a master and an apprentice but that of a service person and a client. The result is the most abominable. I'll abstain from discussing what it means for professors but for the students it ultimately means that they are treated as subhuman beings, i.e., they are considered as having almost no intelligence whatsoever, so instead of lifting the students to the level of the craft, the craft is lowered to their level. This happened in the arts when primitive ancient drawings were declared masterpieces alike to the paintings of Renaissance masters. Like the primitivization of arts led to all monstrosities that fill the "modern art" museum halls, which make me doubt that most modern artists can draw or sculpt at all, this primitivization of mathematics (whose main expression is presenting the mathematics as a mere taxonomy, a bunch of simple algorithms, and the art of pushing calculator buttons) will inevitably lead to reverting the craft to its pre-Greek level. Moreover, I have read a couple of math. education papers that, after you remove all fancy buzzwords from them, advocate exactly this transition.

3) Many mathematicians lost all pride and turned into mere beggars for money (grants, salary increases) and recognition (competition for prizes, publications in top journals, etc). I've recently heard some amazing new terminology like "the submission-rejection cycle" (you submit to a journal, get rejected, submit to another one, get rejected, etc.).

4) There is no hope for fundamentally new weapons that can be developed soon using further advances in pure math. This removed the need for rigorous mathematical education for military purposes and made the math. education a purely political issue. Despite all my disgust towards the wars, I have to grant the military the basic common sense: they have a clear goal to beat the enemy and whatever can serve this goal will be promoted and maintained at the operational level. The politicians need only to please the electorate for whom they coined the wonderful name "taxpayers". It doesn't matter how much a "taxpayer" knows about the science. As long as it is done on his money, he is the boss and he is the one to tell the right from the wrong. Moreover, even when the taxpayers do have common sense, their representatives in the legislature usually don't.

5) The Platonic idea of mathematics as an objective (super)reality was replaced by the idea of mathematics as sociological and cultural phenomenon. Note the words "mathematics is on the edge of a philosophical breakdown since there are different ways of convincing and journals only accept one way, that is, proof". They show clearly that the person saying them has lost all sense of an explorer of an unknown land whose task is to find out what is there and to make sure that what he sees is not a fata morgana. His goal now is merely to "convince other people of something".

I can continue, but I guess you got the idea by now. We are no longer viewed as high priests, or explorers, or technical experts, but rather as street sellers of strange and hardly digestible goods by the general public (which would be still tolerable) and by ourselves (which is suicidal, IMHO).

There is still a simple remedy: behave with pride and teach the craft properly whenever you can do it without losing your means of living immediately. I have little hope that this remedy will be applied widely, but you can always do it locally. And the last piece of advice: do not lose your sleep over the opinions of other people and do not argue with them. Look at what real results they achieved with their approach instead. If they have nothing to put on the table, just consider them a bunch of flies. The fly buzz can be quite irritating and some flies can deliver a venomous bite, but still a fly is a fly and a human is a human (not because a human has two eyes and a nose and the fly has a pair of wings as the modern humanists try to convince us, but because a human can absorb the whole Universe and to transcend his temporal and spatial limits and his self-centeredness, while the fly will always see only the piece of honey or shit it can feed on at the next moment).

Answer by fedja for Expected edit distance

2013-05-05T16:47:00Z

I am not sure there is any proven lower bound so far however.

This should really be a comment but it is too long.

A lot depends on how good lower bound you want. The trivial one can be obtained by just saying that if we have $k$ deletions, $k$ insertions, and $m$ substitutions, we can get just ${n\choose k}^2{n-k\choose m}$ new sequences from a given one. Now, if that is much less than $2^n$ for every $k,m$ with $2k+m < cn$, then the limit is at least $c$. Using the simple approximation $m!\approx m^me^{-m}$, we see that all we need is to ensure that $$ 2\mu\log\mu+(1-\mu)\log(1-\mu)+\nu\log\nu+(1-\mu-\nu)\log(1-\mu-\nu)>-\log 2 $$ whenever $2\mu+\nu\le c$, which (after some computations) yields $c>0.18$. Of course, this is very crude because it doesn't take into account the fact that the number of ways to convert one sequence into another within the edit distance is typically exponential in $n$ too.

Answer by fedja for textbooks on asymptotic expansions

2013-04-16T17:54:44Z

De Bruijn's "Asymptotic methods in analysis" is an excellent book for beginners. You'll need to work through it diligently to learn everything but no advanced a priori knowledge is required. Also, you can easily download it from many online places that do not worry too much about copyright and, even if you decide to stay law-abiding, it goes for under ten bucks on amazon.

Cool problems to impress students with group theory

2010-01-29T02:08:04Z

Since this forum is densely populated with algebraists, I think I'll ask it here.

I'm teaching intermediate level algebra this semester and I'd like to entertain my students with some clever applications of group theory. So, I'm looking for problems satisfying the following 4 conditions

1) It should be stated in the language having nothing whatsoever to do with groups/rings/other algebraic notions.

2) It should have a slick easy to explain (but not necessarily easy to guess) solution using finite (preferrably non-abelian) groups.

3) It shouldn't have an obvious alternative elementary solution (non-obvious alternative elementary solutions are OK).

4) It should look "cute" to an average student (or, at least, to a person who is curious about mathematics but has no formal education).

An example I know that, in my opinion, satisfies all 4 conditions is the problem of tiling a given region with given polyomino (with the solution that the boundary word should be the identity element for the tiling to be possible and various examples when it is not but the trivial area considerations and standard colorings do not show it immediately)

I'm making it community wiki but, of course, you are more than welcome to submit more than one problem per post.

Thanks in advance!

Answer by fedja for Should one attack hard problems?

2013-03-11T04:22:37Z

Actually, I think trying a "hard problem" may be a good idea IF

1) You have a fair evidence that you are strong enough to tackle things other clever people gave up on. The evidence should be tangible. The best evidence is, of course, having solved at least one hard problem already, but that, obviously, cannot be applied to your first hard problem ever. Sometimes a good indication is other people saying something like "You should stop stealing other mathematicians' daily bread and do some real thing that no one else can do!" (Note that you shouldn't follow the first part of this advice.)

2) You have an escape strategy. That may be thinking of something else in parallel, making sure that your plan is such that even a partial progress can be of value, etc.

3) You are not afraid to fail and are used to the feeling of being a hopeless idiot (meaning you can calmly admit this frustrating fact about yourself without any reservations, excuses, or other kinds of self-deceit and still push ahead at your full strength).

4) You have enough free time and do not care too much of your career ups and downs.

5) You are sufficiently open-minded to see things at unusual angles and are trained to figure out reasonably quickly whether any given idea may possibly work or it certainly won't. Note that both are tough skills, which are almost completely untouched in most standard treatises on problem solving.

6) You love the problem. This should, actually, be #0 rather than #6, and it is hard to explain what it means in rational terms, but you can feel it when it happens.

If those conditions are satisfied, go ahead and try shooting the Moon. If not, you'd better make your way up slowly step by step like most of us, picking the fight just slightly bigger than your own size every time.

I'm not a great believer in "having a new idea from the start". The new idea or a combination of ideas usually comes eventually when working on the problem and the moment it comes is often very near the end of the story. The trail of failures that precedes it is well-hidden, but we all start with "I have no method, no feeling, no tools, no clue, and no hope" and proceed through "twisting this, we can get a bit more or something a bit different, however the main difficulty remains untouched". You have to figure out not only what doesn't work but also how exactly it doesn't work. Most of the time is spent on constructing examples and counterexamples to the steps in your initial plan, digressing into simpler models, checking that no information is lost at each particular step, i.e., that if the original theorem is correct, then the intermediate lemma you want to try is at least very plausible, and so on, and so forth. I do not know how it works for others, but for me any non-trivial problem is a scattered jigsaw puzzle, not an originally blurry but complete picture I merely need to focus the camera on.

I'm not sure how much credibility I can claim myself when talking like this about solving hard problems, but, fortunately, most of these claims aren't my creations: I merely believe they are true and the opposites are false. So, take all this with a healthy grain of salt and keep in mind that out of 100 mathematicians, at most 5 are qualified to shoot the Moon in principle and, out of those 5, at most 1 will score a hit when making this long shot, so don't judge us, professors, too harshly when we just know our limitations and are unwilling to try to jump above our heads. There is a lot of stuff at the knee level that needs to be done and some of us (including myself) just feel that it will be more efficient to spend most of our time doing it there. One becomes a loser not when he aims and shoots lower than the Moon but when he stops seeing it in the sky :).

As to the formal question list, I would answer as follows:

Should one attack such hard problems at all?

Yes. The gods won't do it for us, so it'll have to be one of us, poor mortals, who should try.

If one should, why and when? See #1-#6 for "when". As to "why", if one asks this question, one shouldn't.

Will studying hard problems span new ideas?

Possibly. It can work out either way.

Is it even a necessity to understand some hard problems and, especially, why they are hard to solve?

No, nothing is absolutely necessary. You can live and work perfectly well without it.

Or is it just pure waste of time?

This depends on who and what you are.

Or is it that one should learn some hard problems to educate oneself but not spend time attacking them?

That works for some people too.

Answer by fedja for On the $L^1$-norm of certain exponential sums.

2013-03-11T02:00:50Z

As Noam correctly mentioned, the upper bound has to be exponential. However, the exponent can, indeed, be improved.

One (fairly cheap) trick is to look at $|f(x)|^2=2^{|S|}\prod_S(1+\cos 2\pi sx)$. If we can show that the product is bounded from above by $e^{-c|S|}$ outside a set of measure $e^{-c|S|}$, we can get away with Cauchy-Schwarz. Now, $\log(1+y)\le y-cy^2$ for $y\in[-1,1]$ with some $c>0$. Since $2\cos^2 y=1+\cos 2y$, we see that the square term will give us a fixed linear in $|S|$ push down, so it remains to show that for every $a>0$, the set of $x$ for which $\left|\sum_{s\in S} \cos 2\pi sx \right|$ is at least $a|S|$ has exponentially small measure (we'll need to use that twice: once for $x$ and once for $2x$).

This is actually pretty easy if we recall the reverse inequality $\log(1+x)\ge x-Cx^2$ for $x\in[-\frac 12,\frac 12]$, say. Note that the unique representation as a sum property implies that $$ \int_0^1 \prod(1+t\cos 2\pi sx)\,dx=1 $$ for every $t\in\mathbb R$. Assuming that $\sum_{s\in S} \cos 2\pi sx>a|S|$ on a set $E$, choose $t\in(0,\frac 12)$ so small that $b=at-Ct^2>0$. Then, clearly, the product is at least $e^{b|S|}$ on $E$ and the desired exponential bound on the measure of $E$ follows at once. The other set where $\sum_{s\in S} \cos 2\pi sx<-a|S|$ is treated the same way using small negative $t$.

This all is extremely crude, of course. However, it answers the original question in the affirmative, so I'll stop here :).

What is the best probabilistic estimate from below for a random polynomial on an arc?

2012-12-12T01:32:08Z

I'm currently involved in a small (but quite time consuming) project where we are trying to get some decent bound for the number $N(P)$ of real zeroes of a random polynomial $P(x)=\sum_{k=0}^n\xi_k x^k$ where $\xi_k$ are real independent identically distributed random variables satisfying $P(\xi_k=0)=0$ (just to avoid totally idiotic degeneracies) but no other a priori assumptions.

Our current approach uses the inequality $$ \mathcal P\left[\max_{|\alpha|<C\ell}|P(re^{i\alpha})|\le n^{-C}\ell^{Cm}\sum_k|\xi_k|r^k\right]\le e^{-m} $$ for all fixed $r>0$, $0<\ell<1$, $n,m\ge 2$ with some absolute $C>0$, which is not terribly bad and gives the bound $$ \mathcal E N(P)\le C\log^4 n $$ in the end.

However, I suspect that even a stronger bound $$ \mathcal P\left[\max_{|\alpha|<C\ell}|P(re^{i\alpha})|\le n^{-C}\ell^{Cm}\sum_k|\xi_k|r^k\right]\le n^{-m} $$ may hold, which would allow us to shave one logarithm off. I wonder if anybody has any idea of how to get something like this (or better). If you find a counterexample, it'll shed some light on what is going on too. We are currently using the combination of the Turan lemma and the flip-flop around the median technique but all my previous experience shows that using the worst case scenario estimates in the probabilistic setting is never optimal.

To put things in perspective, the bound everybody hopes for should be $\mathcal EN(P)\le C\log n$. It has been proved for many "decent" distributions of $\xi_k$ but if you do not assume anything and require the uniform bound over all distributions (which may be attained at different distributions for different $n$), as in our project, then it looks like the best published bound is $\mathcal EN(P)\le C\sqrt n$ (if somebody knows anything better, I'll be happy to hear it too).

Update: We have finally got $C\log n$ with absolute $C$ in the classical problem (any real i.i.d coefficients) by a different method. However, the question remains because there are interesting situations to which our new approach does not apply but the original one, which gives $\log^4 n$, does.

Answer by fedja for Inequality on Trigonometric polynomials

2013-02-14T06:24:03Z

That is true for all non-negative trigonometric polynomials, though not entirely obvious unless you are a Fourier analyst yourself. To see it, just note that the convolution with $K_{RL}=2F_{2RL}-F_{RL}$ recovers $f$ faithfully and $F_{RL}\le RF_L$. Of course, to Jean such things are as obvious as $2\times 2+1=5$ (he writes $10$ instead of $5$ just out of the traditional analyst's habit to have a 100% security margin in the constants), but I agree that it may be a bit perplexing for poor mortals like you and me. Joe Diestel just told me at a beer party tonight that the most common phrase in Bourgain's early papers was "By standard techniques we conclude from here that". :)

Answer by fedja for submit the second part of a paper

2013-01-07T14:50:46Z

I usually do not split in such cases, but if you do, I guess the same journal is a better choice, especially if you think of the poor people who will have to look up and reference your paper in the future :). Also, if possible at all, I would include into the first part a forward reference to the second one (if the submission is to the same journal and the second acceptance occurs before you get the galley proofs of the first part, that may be completely feasible from the technical point of view). What I really do not understand in this story is how the referee is supposed to do his job being presented with the first part alone. I can imagine myself in his shoes writing something like "The paper has many interesting ideas and no flaws so far but it is completely unclear how the ends will finally meet..."

Center of mass from the abstract point of view, or could the ancient Greeks invent modern analysis?

2012-12-21T04:03:06Z

This is a very open-ended question, which may or may not have a perfect answer, and for which I have a few ideas but nothing like a clear picture. However, I guess it won't hurt to ask to see if people think about such things at all and if they do, what their ideas are. I don't know whether to make it CW or not: on one hand, it is pure mathematics, so we are within the usual set of standards to judge what's right and what's wrong, on the other hand, it is certainly not "a question of the type MO was designed for". So, I'm hesitant to check the community wiki option myself but have absolutely nothing against someone else doing so.

I assume that the ancient Greeks had an idea of a complete normed space ($\mathbb R$ and $\mathbb R^2$ would be enough for our purposes for quite a while), a set, a linear transformation, and the center of mass. On the top of it, I assume they had as much common sense (probably more), as we have nowadays.

The task is the usual one for Archimedes: given a reasonable non-empty set $E$ in a complete linear space $V$, assign a point $C(E)$ to it that you can confidently call "the center of mass". For the purposes of this thread, let's consider bounded at most countable subsets in $V=\mathbb R$ first. If we can figure out what to do with this case to everyone's satisfaction, we can move to the next stage. It may be not a really illuminating model, but it has a few quite funny features already.

The axioms of the center of mass are just the common sense ones:

1) The center of mass is never outside the closed convex hull of the set.

2) If $A$, $B$ are disjoint, then $C(A\cup B)\in[C(A),C(B)]$.

3) If $T$ is an affine transformation, then $C(TE)=TC(E)$.

4) (this is a bit tough, so feel free to drop or to modify it if it helps) If $A,B$ are such that the sets $a+B$, $a\in A$ are disjoint, then $C(A+B)=C(A)+C(B)$

I don't know if we really need anything else (in particular, I'm not sure if the addition of the "obvious" definition of the center of mass of a finite set is needed, helpful, or hurtful), but feel free to play with this list in any reasonably way you want.

The questions are the usual ones:

A) Existence

B) Uniqueness

C) Way to find $C(E)$ given $E$.

Any ideas, constructions, counterexamples, references, etc. (not necessarily restricted to the model I described) are welcome :).

Edit: Thanks to everyone who responded! Let me clarify one thing. Yes, if we can create a meaningful notion of mass (say, if there exists a translation invariant Borel measure that is finite and positive on $E$), we can define the center of mass in the usual way and the only question will be if the definition is unambiguous. However, if I give you a symmetric set, you'll not hesitate to say that the center of symmetry is also the center of mass. Also, if I give you an infinite set and add one point to it, you'll probably (but not necessarily) agree that the center of mass won't feel this addition, the reason being that the set was infinitely times more massive than the point we added not as mush because we can measure the actual mass in some way but merely because infinitely many disjoint shifts of the point fit inside the set. In other words, quite often we can determine the relative size without being able to assign any meaning to the absolute size. This is one of the loopholes in the integration theory I'd like to exploit and see how far one can get with it. In a sense, that is a straight extension of the original Eudoxus line of thinking, which is why "ancient Greeks" entered the title of the question.

Answer by fedja for Publishing a bad paper?

2012-12-19T03:59:59Z

While it is true that if you have 5-6 good research papers after that, nobody will care about what you wrote in that paper (assuming it is as bad as you present it), if it is one of your only 3 official publications by the moment of the job search (whether you include it into your CV or not doesn't matter because once you reach the short list, the mathscinet and the grapevine become more important sources of information about you than your own presentation of yourself) and the other two papers are not readily available, you are a toast.

One thing you can do is to check quickly if what you've done is, indeed, well-known in some form. If it is, you are off the hook because knowingly publishing a published result as new is a no-no, so you may just regretfully say that somebody has "undercut" you there and you need to work on another project now. Whether there is any other clean exit depends on many details you haven't provided and many people gave you good advice already, so I'll stop here.

Answer by fedja for The Unreasonable Effectiveness of Physics in Mathematics. Why ? What/how to catch?

2012-12-16T23:59:52Z

My opinion is that physicists transferred from study of "individual objects" to that of "large systems" where the order arises from limit probability laws rather than from simple deterministic formulae and from the study of something "readily observable" to something that is, essentially, "a purely mathematical object" invisible to a direct experiment. This brought them to the realm traditionally reserved for pure mathematicians. And, of course, with their eagerness to use whatever tools they have available in any way that is short of total lunacy, they went on to make predictions, many of which could be confirmed experimentally, leaving a long trail of successes and failures in their wake for mathematicians to explain.

I do not know the situation with the string theory and low dimensional topology but I have some idea about what's going on in random matrices (thanks to Mark Rudelson and his brilliant series of lectures) and in percolation/random zeroes (thanks to Stas Smirnov and Misha Sodin). The thing that saves physicists from making crude mistakes there is various "universality laws".

Here is a typical physicist's argument (Bogomolny and Schmidt). You want to study the nodal domains of a random Gaussian wave $F$ (the Fourier transform of the white noise on the unit sphere times the surface measure). Let's say, we are in dimension 2 and want just to know the typical number of nodal lines (components of the set $\{F=0\}$) per unit area. The stationary random function $F$ has only a power decay of correlations. However, we ignore that and model it with a square lattice that has the same length per unit area as $F$ (this is a computable quantity if you use some standard integral geometry tricks). Now, at each intersection of lattice lines, we choose one of the two natural ways to separate them (think of the intersection as of a saddle point with the crossing lines being the level lines at the saddle level). Then, we get a question (still unresolved on the mathematical level, by the way) about a pure percolation type model. Thinking by analogy once more, we get a numerical prediction.

From the viewpoint of a mathematician, this all is patented gibberish. There is no way to reduce one process to another (or, at least, no one has the slightest idea how this could be done as of the moment of this writing). Still, the Nature is kind enough to make the answers the same or about the same for all such processes and Mathematics is powerful enough to provide an answer (or a part of an answer) for some models, so the physicists run a simulation, and, voila, everything is as they predicted and we are left with 20 years or so worth of work to figure out what is really going on there.

I'm not complaining here, quite the opposite: this story is really quite exciting and the work mentioned is both real and fascinating. We are essentially back to the days when Newton tried to explain the nature of gravity looking at Kepler's laws trying various options and separating what works from what doesn't. I'm only saying that the famous "physicists' intuition", which is so overrated, is actually just the benevolence of Nature. Why should the Nature be so benevolent to us remains a mystery and I know neither a physicist, nor a mathematician, who could shed any light on that. The best explanation so far is contained in Einstein's words "God is subtle, but not malicious", or, in a slightly less enigmatic form, "Nature conceals her mystery by means of her essential grandeur, not by her cunning".

Answer by fedja for Convex optimization problem to QPP

2012-12-09T04:49:29Z

For what it is worth, I played a bit with the non-constrained optimization of this type and noticed a strange thing. Suppose that you want to minimize $\sum_i a_i\max (F_i(x),0)^2$. Choose any $y$. Introduce auxiliary variables $u_i$ initially set to $1$. Find the minimum of $\sum_i a_i u_i (F_i(x)-\min(0,F_i(y))^2$. Look at the corresponding point $x$ and update $u_i$ as follows: if $F_i(x)>0$, put $u_i=1$, otherwise divide $u_i$ by $4$, say. Then update $y$ to $x$ and repeat. There seems to be no particular reason why that should converge at all. However in practice 20 iterations seem to be enough for $20$ variables and $12000$ random forms. I wonder what happens if you do the same calling the QPP solver to find the restricted minimum at each stage. Note that you can easily recognize the solution once you've found it: as soon as $y$ is close to $x$ and all $u_i$ corresponding to $F_i(x)<0$ are small, we are done. Also, since we are not guaranteed against degeneracies, I added the quadratic form $a(x-y)^2$ where $a$ is changing at every step and is roughly $0.01$ times the trace of the matrix in the current quadratic minimization problem divided by the number of variables.

I guess Rudi's answer may be much better, but my naiive approach is very easy to implement :).

Answer by fedja for Generic words of given weight

2012-11-29T03:04:47Z

Sorry for the long silence. Believe it or not, it was impossible to find even 10 minutes until now, not a full hour I need to explain everything in a decent way. Even now I'm starting but I'm not at all sure I'll finish. I'll try to do it in as few shots as possible but I apologize in advance if I will need to bump this thread a few times.

Part 1. Generating functions and counters.

The key idea is that if $A_j$ are some sets of non-negative integers and $N_a$ is the number of ordered representations $a=a_1+a_2+\dots$ with $a_j\in A_j$, then $$ \sum_{a\ge 0} N_az^a=\prod_j\left(\sum_{a_j\in A_j} z^{a_j}\right)\,. $$ Unfortunately, this simplest form is not quite suitable for the weighted letter word counting. However, we can tweak this formula a bit.

Suppose we have an alphabet with letter weights $w_1,w_2,\dots$ and can use any letter any number of times. The number of words of weight $W$ we can create is $$ \sum_{\sum_j \ell_jw_j=W}\frac{\left(\sum_j\ell_j\right)!}{\prod_j\ell_j!} $$ (the standard combination with repetitions formula). Thus, taking into account that $\sum_{\ell\ge 0}\frac{Z^\ell}{\ell!}=e^Z$, we get almost what we want for the coefficient at $z^W$ if we consider the product $$ \prod_j \exp(z^{w_j}) $$
The only problem is that each word is counted not with the weight $1$, as it should in the uniform sampling, but with the weight that is the inverse factorial of its length, which skews the uniform distribution quite a bit. The way to compensate for that is to guess the typical length $L$ and to change the function to $$ \prod_j \exp(Lz^{w_j}) $$ Now, the coefficient is multiplied by $L^{\sum_j\ell_j}$, which is approximately proportional to $\left(\sum_j\ell_j\right)!$ as long as $\sum_j\ell_j\approx L$. As a matter of fact, this weighing emphasizes the words of the length $L$ a bit stronger than it should because $\frac{L^\ell}{\ell!}$ is maximized at $L$. However, as long as $\ell-L=o(\sqrt L)$, the skewing it introduces is negligible. This is what I called the local counting function: the weights are way too much suppressed outside a small window but we hope that outside that window we have only a small portion of words anyway, so suppressing them even further changes nothing in the picture.

If we have a clear idea of what the typical length is, we can introduce all other kinds of counters. To count the number of distinct letters, we need a variable that appears only once if the letter is used at all no matter how many times the letter is used after that. The factor $1+s(e^{Lz^{w_j}}-1)$ does exactly that if you look at the "typical" power of $s$ in the expansion (recall that $\frac{z^{\ell w_j}}{\ell!}$ corresponds to using the $j$-th letter $\ell$ times, so $s$ should appear once if $\ell>0$ and not appear if $\ell=0$). The unique letter counter should appear only if $\ell=1$, so $e^{Lz^{w_j}}-(1-s)Lz^{w^j}$ does the job adding the $s$-factor to the "linear term" in the expansion of the exponent but not anywhere else. You can now play a bit setting various counters yourself to see what generating functions to consider in various cases.

Part 2. The central term extraction.

Suppose now that we have a function $F(s,r)=\sum_{\ell,w}N(\ell,w)s^\ell r^w$ of two variables (you can trivially generalize this to more than two variables as well but I do not want to do the one-variable case because some games you can play with several variables would be invisible there). Suppose that we want to estimate $N(L,W)$. The obvious upper bound (the whole is larger than its part) is $$ N(W,L)\le s^{-L}r^{-W}F(s,r) $$ where we are free to choose $s$ and $r$. Of course, we are going to choose them so that the right hand side is as small as possible. This leads to the minimization problem $$ G(s,r)-L\log s-W\log r\to\min\,. $$ Suppose that $(1,r)$ is a stationary point of the objective function, i.e., the differential vanishes there. Suppose also that, after switching to the variables $\log s,\log r$ (which makes the subtracted terms linear), the second differential is bounded by $A^2(ds)^2+B^2(dr)^2$ near this stationary point. Then we can easily control the sum of all terms that correspond to pairs $\ell,w$ that differ a lot from the pair $(L,W)$ in $F(s,r)$ by looking at $F(se^\sigma,re^\rho)$. We still have $$ N(\ell,w)s^\ell r^w\le e^{-\sigma\ell-\rho w}F(se^\sigma,re^\rho)= e^{-\sigma(\ell-L)-\rho (w-W)} e^{-\sigma L-\rho W}F(se^\sigma,re^\rho)\le e^{-\sigma(\ell-L)-\rho (w-W)}e^{A^2\sigma^2+B^2\rho^2}F(s,r) $$ due to the stationarity and the second derivative estimate.

Now, choosing $|\sigma|=A^{-1},|\rho|=B^{-1}$, we see that $$ N(\ell,w)s^\ell r^w\le \exp(-A^{-1}|\ell-L|+B^{-1}|w-W|)F(s,r)\,, $$ so the terms with $|\ell-L|>A'$ or $|w-W|>B'$ can contribute at most $[Be^{-A'/A}+Ae^{-B'/B}]$ to $F(s,r)$. This crude bound is often enough to show that the main contribution comes from the terms with $w\approx W$, $\ell\approx L$, which sort of allows us to say that the pair $(L,W)$ is typical in the weighted counting where the pair $(\ell,w)$ has the weight $N(\ell,w)s^\ell r^w$. The key idea is that if $s=1$, then this counting is uniform in $\ell$ for each fixed $w$, so getting a typical pair in such weighted counting is essentially the same as getting a typical $L$ for fixed $W$.

Part 3. Circle method and mountain pass.

To be continued...

Answer by fedja for Generic words of given weight

2012-11-27T04:20:41Z

Here is a back of envelope computation. There will be no rigor whatsoever, just a cookbook approach that may be acceptable to a physicist but which every self-respecting mathematician should frown upon. It can give a plausible (but not guaranteed) answer to some of your questions if we just want the general order of magnitude without too high precision but if you want more than that, we'll need to count in honest.

If what I write below looks like gibberish, it's OK. As I said, I just did the calculus, not the actual analysis. If your model corresponds to some physical reality and you know the values of some constants involved, it will be funny to compare them with what follows from my predictions. If you want more, like the distribution laws for the number of occurences of individual letters (or, God forbid, joint distribution for several letters), you need to consult a true expert, not an amateur like myself. In any case, have fun reading and feel free to ask questions. Also watch for idiotic mistakes in algebra: it is quite late here now... :-)

The main local generating function for counting words of weight $W$ assuming typical length about $L$ and decent length concentration (the point is to kill factorials in the denominator; we will still be be off by the factor $e^L$, but we need a typical structure, not the counts).

$F(z,w)=\exp(Lz(w+4w^2+9w^3+16w^4+\dots))=\exp\left(Lz\frac{w+w^2}{(1-w)^3}\right)$

Everything is nice and positive, so the mountain pass in the circle method is a sure bet. We need to find the controlling radius $r$ for the weight $W$, so, for $z=1$, we need to minimize $Lz\frac{r+r^2}{(1-r)^3}-W\log r$. Alas, we are certain to end up with $r$ noticeably less than $1$, so we have to differentiate in honest: $$ r\frac{4+r-2r^2}{(1-r)^4}=\frac WL $$ We also need the consistency equation, which says that we, indeed, get $L$ as a typical length with $z=1$, i.e., $\frac\partial{\partial z}(Lz\frac{r+r^2}{(1-r)^3}-L\log z)|_{z=1}=0$, i.e., $r+r^2=(1-r)^3$ so $r=0.284774761\dots$ and $W/L=4.486414\dots$.

This is a bit counterintuitive because it predicts, in particular, that the typical word consists mainly of the letters of low weights and the option to diversify, which should lead to more possibilities, is really pretty useless. Let's run the sanity check. Suppose that we are looking at words using a few low weight letters. Then they are just $A^W$ with some fixed $A>1$. Let us add a letter of weight $n$ in proportion $p$. We get the new number about $A^{(1-pn)W}\left(\frac ep\right)^{pW}$, so to get the largest count, we have to solve $Cn=-\log p$ whence the portion of letters of length $n$ is decaying exponentially in $n$. Thus, the cost of diversification is prohibitively high here and the answer we got makes sense.

Now, how many different letters typically? The generating function to consider now is $$ G(s)=\prod_{k\ge 1}[1+s(e^{Lr^k}-1)]^{k^2}\,. $$ The typical number $D$ of distinct letters would correspond to the zero derivative of $\log G(s)-D\log s$ with respect to $s$ at $1$. Thus, we expect something like $$ \sum_k k^2(1-e^{-Lr^k})\approx\int_0^\infty t^2(1-e^{-Le^{-\rho t}})\,dt $$ where $\rho=-\log r$. The second factor is just a sharp cutoff at $t=\frac{\log L}{\rho}\approx\frac{\log W}{\rho}$, so, let's say $$ D\approx \frac 1{3\rho^{3}}\log^3 W= 0.168209\log^3 W. $$

What's next? Ah, the typical number $U$ of letters appearing once! Now we need to place $s$ only on one term in the exponent, so we go to $$ H(s)=\prod_{k\ge 1}[e^{Lr^k}-Lr^k(1-s)]^{k^2}\,. $$ Same routine with setting the derivative of $\log H(s)-U\log s$ to $0$, we get $$ H\approx\sum_k k^2 Lr^k e^{-Lr^k}\,. $$ This one is harder because we run through the bump very quickly, i.e., in constant time. It also suggests an "oscillating asymptotics", i.e., that the arithmetic nature of $W$ introduces an effect that does not decay with size. However, we can still play our usual game around $\log L/\rho$ and get the quasi-asymptotics $$ 0.7927\log^2 W \le U\le 0.7996 \log^2 W\,. $$ Alas, as I said, the quasi-asymptotics is, probably, all we can hope for here.

Answer by fedja for shallow question: Why a 300 digit number is associated with "any NP-hard problem"?

2012-11-26T06:21:35Z

No matter how you formalize the question, if we believe that this world is not a computer simulation with a program of decent length with all randomness introduced by some simple standard pseudorandom generator but a truly random chain of events, then it looks like a rare moment of true unforgivable ignorance of Donald Knuth. He had no excuse for not knowing http://en.wikipedia.org/wiki/Kolmogorov_complexity. It is actually much easier for me to believe that gods had a direct communication with him and showed him a part of the program somehow than to believe that he didn't know what he was talking about to the extent described. Well, perhaps this was the case and we are just funny configurations in some game with simple rules (it was Knuth who designed "life", wasn't it?) but I prefer to act under the alternative assumptions, at least for the next few years :).

Answer by fedja for lines through A_n reflection arrangement and permutations

2012-11-24T13:08:08Z

I'm not sure if I understand the question correctly, but stripped of all high tech language, it seems to be "Having $n$ runners on the road, can we arrange any order of their pairwise meeting times?". In this formulation, the answer is clearly "No". Assign one runner as a standing checkpoint. Then if the two runners meet outside the interval bounded by their checkpoint crossings, they have to run in the same direction and if they meet inside that interval, they must to run in the opposite directions. Now let the relative time arrangement be

checkpoint1=1, checkpoint 2=3, checkpoint3=4,

meeting12=5, meeting23=6, meeting 13=2.

i.e., the corresponding impossible permutation is (2,3)(1,2)(3,0)(2,0)(1,3)(1,0).

Answer by fedja for Largest subarray with average $\geq$ k

2012-11-14T23:16:31Z

If you are not in the mood to go to the library right away, here is a simple description:

1) Subtract $\kappa$ from everything ($N$ operations).

2) Replace $a_k$ by the partial sums $S_k=\sum_{j=1}^k a_j$ ($N$ operations).

Now you are looking for the pair $0\le k\le m\le N$ such that $S_k\le S_m$ with the largest difference $m-k$. Note that $S_k$ is necessarily the minimum of $S_1,\dots,S_k$ and $S_m$ is necessarily the maximum of $S_m,S_{m+1},\dots,S_{N-1}$. Don't forget $S_0$ (the empty sum)!

3) Mark all such minima going from the left and all such maxima going from the right ($5N$ operations or so). You will have a decreasing sequence of positive starting positions and a decreasing sequence of positive ending positions.

4) Start with the leftmost starting position and go along the possible ending positions from the left to the right until you get the rightmost that still works. Record the difference. Go to the next starting position and see how far you can move the ending position to fit now. Compare the difference with the previous one and record it if it is larger.

5) Repeat until you reach the end.

Note that you go left to right all the time never coming back, so these steps are linear as well. Probably, you can optimize a bit but I'm too lazy to think of how.

6) Once you finish debugging the program and get some free time, follow Gerhard's advice :).

Editing with response to comments:

I'm not sure what you guys are doing that it doesn't work for you, but here how it runs on

2 2 -1000 -1000 2 2 -2 2 2 2 2 -2 -2 2 2 -1000 -1000 2 2 2

with average 2:

Step 1: remove 2:

0,0,-1002,-1002,0,0,-4,0,0,0,0,-4,-4,0,0,-1002,-1002,0,0,0

Step 1: partial summation left to right:

0,0,0,-1002,-2004,-2004,-2004,-2008,-2008,-2008,-2008,-2008,-2012,-2016,-3018,-4020,-4020,-4020,-4020.

Step 3:

Min positions (strict!) counting from the left:

0: 0, 3: -1002, 4: -2004, 7: -2008, 12: -2012, 13: -2016, 14: -3018, 15: -4020,

Max positions (strict) counting from the right:

2: 0, 3: -2002, 6: -2004, 11: -2008, 12: -2012, 13: -2016, 14: -3018, 18: -4020,

Steps 4,5. Put the marker B (beginning-1) and E (end) at the leftmost possible positions: B=0,E=2. Record the length 2 and the interval [1,2]

Try moving E to the right with this B. Impossible.

Change B to 3 (value -1002). Try to move E to the right. Impossible

B=4 (-2004) Now E can go to te right to 6 (-2004). Same length. No record.

B=7 (-2008) E goes (from the previous position, not from the beginning!) to 11 (-2008) Length 4>2, interval [8,11]. Record.

B=12 (-2012) E goes to 12. Length 0, no record.

B=13 (-2016), E goes to 13. Length 0, no record.

B=14 (-3018), E goes to 14. Length 0, no record.

B=15 (-4020), E goes to 18. Length 3<4, no record, reached the end, terminate, output [8,11].

Answer by fedja for Deciding whether or not an exponentially distributed random variable exists in a set via the use of a "black box" function

2012-11-21T01:41:55Z

OK, here is what I have. I'll skip some derivations (I'll provide them later if you are interested) and just describe the conclusions. The final tables apply if you have noiseless data. Any noticeable amount of noise will cost you quite a bit here.

The problem of how to distinguish between two fixed densities $p(x)$ and $q(x)$ is classical. Suppose that we want to bound the combined probability of error by some small $\theta>0$. This means that if we are allowed to take $n$ samples, we have to find some set $E\subset\mathbb R^n$ such that $\int_E P+\int_{E^c}Q\le\theta$ where $P(x_1,\dots,x_n)=p(x_1)\dots p(x_n)$ and similarly for $Q$. Here $E$ is the set where we declare $q$ to be actual density. Note that in no way can this sum be better than $\int\min(P,Q)$ and we can achieve that by the standard maximal likelihood decision: we declare the density $Q$ if $P(X_1,\dots,X_n)<Q(X_1,\dots,X_n)$ and $P$ otherwise. We also can get a fairly clear idea of the necessary sampling size. In fact, we can tell it almost up to a factor of $2$. Note that $\min(P,Q)\le\sqrt{PQ}$, so $$ \int\min(P,Q)\le \left(\int \sqrt{pq}\right)^n $$. On the other hand, $$ \left(\int \sqrt{pq}\right)^{2n}=\left(\int \sqrt{PQ}\right)^{2}\le \left(\int\min(P,Q)\right)\left(\int\max(P,Q)\right)\le 2\int\min(P,Q) $$ Thus, if $\int\sqrt{pq}=e^{-H}$, then to reach the level $\theta$ of combined error, we need at least $\frac 12 H^{-1}\log\frac 1{2\theta}$ and $H^{-1}\log\frac 1\theta$ samples will suffice.

The problem with your case is that we test not two densities but two families of densities against each other. However, if my computations are correct, we are lucky and the likelihood test that distinguishes the worst pair is actually universal enough to achieve the level of confidence given by the above $\sqrt{pq}$ estimate. So assuming that $\lambda_q=w$ (so every other $\lambda$ is $\ge 1$), we can define $p_L(x)=\frac{N-1}N Le^{-Lx}+\frac 1Nwe^{-wx}$, $q(x)=e^{-x}$ where $L=L(N,w)$ is determined from the maximization problem $\int\sqrt{p_Lq}\to\max$ (which in practice is better to pose as $H=\frac 12\int(\sqrt{p_L}-\sqrt q)^2\to\min$), then the corresponding maximal likelihood text works fine and gives a guaranteed bound $\theta$ for each one-sided error whenever the $\sqrt{pq}$ estimate yields the combined error of $\theta$.

I ran a small program to see what sampling sizes it gives for reasonable $w$ and $N$. The table for the sacramental $\theta=0.05$ is below. The lines are $N,L,n$. \phantom{+} is the artifact of the automatic LaTeX style formatting that I was too lazy to disable. As you can see, with your $10^5$ samples you are just on the edge of "theoretically feasible" for $w=0.5,N=100$ but if you can drop either number, everything gets fairly nice (if no noise is present, of course).

I suggest you run a few simulations and see whether it works for you (the "general theory" should be OK, but I could make some stupid mistakes somewhere). Normally, you are getting something like $$ n=8N^{\frac 1{1-w}}\log\frac {1}{\theta} $$ as a rule of thumb for choosing the sample size. This is all "the best performance in the worst case" approach. If you actually have more information than you put in the post, that may help push the numbers down a bit :).

Feel free to ask questions but do not expect a quick answer: life is crazy at this end...

w=0.5
 100  \phantom{+} 1.009397  186378
  90  \phantom{+} 1.010406  155814
  80  \phantom{+} 1.011662  127611
  70  \phantom{+} 1.013269  101830
  60  \phantom{+} 1.015398   78546
  50  \phantom{+} 1.018358   57847
  40  \phantom{+} 1.022762   39849
  30  \phantom{+} 1.030037   24705
  20  \phantom{+} 1.044454   12637
w=0.45
 100  \phantom{+} 1.010954   89813
  90  \phantom{+} 1.012108   75790
  80  \phantom{+} 1.013540   62719
  70  \phantom{+} 1.015367   50637
  60  \phantom{+} 1.017779   39584
  50  \phantom{+} 1.021120   29613
  40  \phantom{+} 1.026065   20790
  30  \phantom{+} 1.034179   13204
  20  \phantom{+} 1.050103    6985
w=0.4
 100  \phantom{+} 1.012550   45454
  90  \phantom{+} 1.013842   38711
  80  \phantom{+} 1.015442   32363
  70  \phantom{+} 1.017476   26429
  60  \phantom{+} 1.020152   20932
  50  \phantom{+} 1.023843   15900
  40  \phantom{+} 1.029277   11371
  30  \phantom{+} 1.038131    7392
  20  \phantom{+} 1.055337    4039
w=0.35
 100  \phantom{+} 1.014103   24058
  90  \phantom{+} 1.015519   20670
  80  \phantom{+} 1.017266   17449
  70  \phantom{+} 1.019481   14406
  60  \phantom{+} 1.022385   11553
  50  \phantom{+} 1.026372    8904
  40  \phantom{+} 1.032211    6480
  30  \phantom{+} 1.041659    4307
  20  \phantom{+} 1.059842    2427
w=0.3
 100  \phantom{+} 1.015495   13254
  90  \phantom{+} 1.017009   11481
  80  \phantom{+} 1.018872    9781
  70  \phantom{+} 1.021226    8158
  60  \phantom{+} 1.024301    6619
  50  \phantom{+} 1.028504    5172
  40  \phantom{+} 1.034628    3826
  30  \phantom{+} 1.044470    2597
  20  \phantom{+} 1.063235    1506
w=0.25
 100  \phantom{+} 1.016562    7561
  90  \phantom{+} 1.018136    6600
  80  \phantom{+} 1.020067    5670
  70  \phantom{+} 1.022499    4775
  60  \phantom{+} 1.025664    3917
  50  \phantom{+} 1.029973    3099
  40  \phantom{+} 1.036219    2328
  30  \phantom{+} 1.046192    1611
  20  \phantom{+} 1.065043     960
w=0.2
 100  \phantom{+} 1.017079    4443
  90  \phantom{+} 1.018656    3906
  80  \phantom{+} 1.020587    3382
  70  \phantom{+} 1.023011    2873
  60  \phantom{+} 1.026156    2380
  50  \phantom{+} 1.030419    1906
  40  \phantom{+} 1.036571    1453
  30  \phantom{+} 1.046335    1024
  20  \phantom{+} 1.064644     625
w=0.15
 100  \phantom{+} 1.016716    2675
  90  \phantom{+} 1.018218    2367
  80  \phantom{+} 1.020052    2064
  70  \phantom{+} 1.022349    1768
  60  \phantom{+} 1.025319    1478
  50  \phantom{+} 1.029333    1197
  40  \phantom{+} 1.035099     924
  30  \phantom{+} 1.044204     662
  20  \phantom{+} 1.061157     414
w=0.1
 100  \phantom{+} 1.014952    1647
  90  \phantom{+} 1.016263    1466
  80  \phantom{+} 1.017861    1287
  70  \phantom{+} 1.019857    1111
  60  \phantom{+} 1.022433     937
  50  \phantom{+} 1.025903     766
  40  \phantom{+} 1.030871     599
  30  \phantom{+} 1.038684     436
  20  \phantom{+} 1.053150     278
w=0.05
 100  \phantom{+} 1.010786    1099
  90  \phantom{+} 1.011716     983
  80  \phantom{+} 1.012849     868
  70  \phantom{+} 1.014262     754
  60  \phantom{+} 1.016083     641
  50  \phantom{+} 1.018533     528
  40  \phantom{+} 1.022034     417
  30  \phantom{+} 1.027529     308
  20  \phantom{+} 1.037677     200

Answer by fedja for Schwarz type inequality

2012-11-17T05:07:34Z

Looks like we are closing the question anyway, so I'll just provide a counterexample quickly before the final vote is cast.

If you think a bit of what is asked and what the natural freedoms and scalings are present here, you'll see that it is enough to get an analytic $f$ in the right half-plane $x>0$ ($z=x+iy$ as usual) such that $|f|<1/x$ and $|f'(1)|>1$. Now just take something like $f(z)=\frac 1z-aze^{-\sqrt{z}}$ with sufficiently small positive $a$. I leave it to somebody else to beat $4$ in the upper bound.

As to "motivation" in general, look up in the evening. You'll see the stars in the sky. What other motivation do you need?

Answer by fedja for Maximizing number of factors contributing in the sum of sorted array bounded by a value

2012-11-16T05:06:16Z

This seems to work, but you'd better check for idiotic mistakes :).

import math;

srand(23);

int N=60;

int[] a;
for(int k=0;k<N;++k) a[k]=rand()%55;
a=sort(a); 


int B=18;

a[N]=a[N-1]+B+1;

int K=0,k=0,m=0,s=0,S=0;

while(true)
{
while((k+m<N)&&(S<=B))
{
++m; S+=a[k+m]-a[s]; s+=m%2;  
K=k; 
}
if (k+m==N) {write(K,m-1); break;}
else {++k; ++s; S+=a[k+m]-a[s-1]-a[s-m%2]+a[k-1];} 
}

write(a);
pause();

Answer by fedja for Examples of statements that provably can't be proved using a promising looking method

2012-11-16T03:12:51Z

This is an old thread but since it got revived, I like the following completely elementary example:

Statement A: A disk of diameter one cannot be covered by strips of total width less than 1.

Proof: Look at the hemisphere over this disk. The area of the spherical strip is proportional to the width regardless of the position and the trivial area comparison finishes the problem off.

Statement B: An equilateral triangle with altitude of length one cannot be covered by strips of total width less than 1.

One would be certainly tempted to try something similar to the previous approach until he realizes that the proof above also shows that you cannot cover the disk twice by strips of total width less than 2. However it is easy to cover the triangle twice by 5 strips of width 1/3 each.

Answer by fedja for Provable zero-free region for any entire function that analytically is similar to zeta(s)

2012-11-10T22:13:00Z

OK, shameless cheating, as promised.

Part 1. Let's start with something.

We need a function bounded in $\Re z>1$ and growing not too fast on each vertical line whose zeroes are somewhere on the left. The first thing that comes to mind is $1$. No zeroes anywhere in sight, beautiful control on vertical lines. All that is lacking is the unboundedness on $\Re z=1$.

Part 2. Push it up!

We now want to add some bumps on the uneventful road $\Re z=1$. It is natural to add one bump a time. We have two options for bumping: addition and multiplication. Since we want to control the zeroes without trouble, we'll use multiplication. So, we'll be looking for an infinite product.

Part 3. A tiny little bump.

Take some entire function $g$ bounded by $1$ in the right half-plane, tending to $0$ at infinity in any right half-plane, and attaining its maximum of absolute value in $\Re z\ge 1$ at $1$, where it is real and positive. Denote $g(1)=a>0$. The exact choice doesn't matter. I'll take $g(z)=\frac{1-e^{-z}}{z}$. Put $F(z)=1+g(z)$. Now the ride along the line $\Re z=1$ is not that smooth anymore: you have to ascend to a small hill at $1$. However, at infinity everything levels to $1$ uniformly in any right half-plane. Also, if there are any zeroes, they all have non-positive real parts.

Part 4. Amplify the bump (being naive and fair)

Just raise $F$ to a high power $N$. You'll get as huge bump as you want. The problem is that it also becomes huge well to the right of $1$.

Part 5. Discriminate against numbers with the large real part.

Replace $g(z)$ by $g(z)e^{-n^2z}$. Of course the value at $1$ will suffer enormously, but everything with real part greater than $1$ will suffer much more (which is the whole point of any true discrimination).

Part 6: Amplify with discrimination.

Raise $F(z)=1+g(z)e^{-nz}$ to the power $N$. We'll get $(1+ae^{-n^2})^N$ at $1$ but only at most $(1+ae^{-n^2-2n})^N$ for $\Re z>1+\frac 2{n}$. Choose $N\approx a^{-1}e^{n^2+n}$. We'll get about $e^{n}$ at $1$ and at most $1+2e^{-n}$ to the right of $1+\frac 2n$. Now it is quite a bump, and it is next to invisible just a tiny bit to the right of $1$.

Part 7: Ship it up the line to satisfy the local regulations.

Replace $F(z)^N$ with $F(z-iy_n)^N$ with large $y_n$ to satisfy the polynomial growth restriction in $\Re z>-n$: let's even make $|F(z)^N-1|<2^{-n}(1+|z|)^{2^{-n}}$ in $\Re z>-n$. Remember that though our bump function is huge, it is still bounded in any right half plane and levels to $1$ at infinity there. We also have $|F(z)|^N\le 1+2e^{-n}$ when $\Re z>1+\frac 2n$ regardless of the shipment.

Part 8. Put the production and shipment of bumps on the conveyor belt with $n=1,2,3,...$, and enjoy the product.

Of course, this is as shameless, abominable, and mostly illegal as any manufacturing under loose government regulations. Every loophole that could be exploited in the formulation of the problem has been exploited. So, please, do not accept or upvote. Instead, think of how to tighten the regulations to force someone to do honest work. :)

Answer by fedja for Projections in Banach spaces

2012-11-10T00:29:46Z

I'm not sure if I like the ultrafilters, so I decided to find some elementary construction. I do not have much imagination for chains of commuting projections either, so let us consider the space of all functions $f:[0,1]\to X$ where $X$ is the space of all sequences and let $P_s$ just keep the values to the left of $s$ and kill the values to the right of $s$. So far so good. The operator $Q$ will just act in each layer separately, so it is going to be an operator in $X$ really. The devil is in the choice of the norm. We need to take an advantage of small support somehow, which calls for considering a sequence of $L^{p_k}$-norms on $[0,1]$ with decreasing $p_k>1$. Then we'll have the full strength of Holder backing us. However, there needs to be some penalty for using norms with small $p_k$, so it is natural to pair each $p_k$ with some norm $N_k$ in $X$, which are increasing fast so that the final norm, which is just the infimum of $\sum_k\|N_k(f_k(t))\|_{L^{p_k}}$ over all decompositions $f=\sum_k f_k$ will have to be a hard trade-off rather than a trivial collapse to a single term. Now the first thing we want is $$ N_{k+1}(Qx)\le N_k(x) $$ This will ensure that for the first small $k$ we will fire with Holder to gain on the power of the length of the interval but for the large $k$, when Holder finally betrays us and the reduction of power becomes useless, we will use $$ N_k(Qx)\le 2^{-k} N_k(x) $$ so each faraway term will just take care of itself. The possibilities for the choice of such family of norms and $Q$ are unlimited but, being (sort of) an analyst, I like the backward shift and weighted spaces, so put $$ (Qx)_{j}=2^{-j}x_{j+1}, $$ and $$ N_k(x)=\sum_j 2^{kj}|x_j|. $$

Answer by fedja for Density of integers $n$ whose totient $\varphi(n)$ is larger than $\alpha n$

2012-11-05T20:23:49Z

Anonymous gave a perfect answer already. All I want to add to it is that you do not need to be Erdos or even Schoenberg to figure such things out. I'll just show how to establish the existence of density for $\alpha>0$, leaving the rest to you.

The starting point is that we know that for a pair of integers not exceeding $N$, to have a common divisor is a not very probable event and to have a large common divisor is a really rare event. Indeed, the number of pairs $(m,n)\in [1,N]\times [1,N]$ such that some fixed number $d$ divides both $m,n$ is at most $N^2/d^2$, so the number of pairs having a common divisor greater than $D$ is at most $N^2\sum_{d\ge D}d^{-2}\le N^2/(D-1)$.

Now, fix some $D$ and denote by $\Phi_D(n)$ the number of numbers $m\le n$ such that both $m,n$ are divisible by some prime $p>D$. What we just proved shows that $\frac 1N\sum_{n\le N}\Phi(n)\le \frac 1{D-1}$, so for every $\varepsilon>0$ we can be sure that the upper density of $n$ for which $\Phi_D(n)>\varepsilon n$ is less than $\varepsilon$ if $D$ is chosen large enough.

Let now $\varphi_D(n)$ be the number of $m\le n$ such that $m$ and $n$ have no common prime divisor less than $D$. Note that $\varphi_D(n)-\Phi_D(n)\le\varphi(n)\le\varphi_D(n)$ and $\Phi_D(n)$ is usually less than $\varepsilon n$. On the other hand, $\varphi_D(n)/n$ is completely determined by the remainder of $n$ modulo the product of primes less than $D$, so if we replace $\varphi$ by $\varphi_D$, the existence of density problem becomes trivial. Note that we can do it outside a set of arbitrarily small upper density with arbitrarily small error. So, the only problem may arise when the small error is not tolerable, i.e., when $\alpha$ is such that for all $\varepsilon>0$ the set of numbers $n$ with $\frac{\varphi(n)}n\in(\alpha-\varepsilon,\alpha+\varepsilon)$ has upper density bounded from below by some $c>0$ independently of $\varepsilon$.

The last step is to show that it is impossible. Let the upper density of the set $S_\varepsilon=\{n:|\frac{\varphi(n)}n-\alpha|<\varepsilon\}$ be greater than $c$ regardless of $\varepsilon$. Then the upper density of the set $S_D=\{n:|\frac{\varphi_D(n)}n-\alpha|<2\varepsilon\}$ is at least $c/2$ if $D$ is large enough. But $S_D$ has density, so, going back, we conclude that the lower density of $S_{3\varepsilon}$ is at least $c/4$. Now let $p$ be any prime greater than $8/c$. Let $S(p)=\{n\in S_{3\varepsilon}:p\not\mid n\}$. Then the lower density of $S(p)$ is at least $c/8$. Note now that $pS(p)$ has numbers with $\frac{\varphi(n)}n\approx \alpha(1-\frac 1p)$ up to $\pm 3\varepsilon$. If we take sufficiently large finite set $P$ of primes $p>8/\delta$ (the primes to choose depend on $c$ only), we'll get the disjoint sets $pS(p)$ (the disjointness will be guaranteed if $\varepsilon$ is so small that the $3\varepsilon$-intervals around the points $\alpha(1-\frac 1p)$ do not overlap) of lower density $\frac c{8p}$. However, we can choose $P$ so that $\frac c 8\sum_{p\in P}\frac 1p>1$, which is a clear contradiction.

Needless to say, the full Erdos-Wintner theorem is much deeper than this and is certainly worth learning if you like the elementary number theory.

Answer by fedja for Integer partition and sum of squares

2012-11-04T13:16:26Z

Let $N$ be the number you want to get as a sum of squares. Let $k$ be the first number to square. Then $N$ is $n$-squareable if $N-k^2$ is $n-k$ squareable, right? Now let's play the usual game. Suppose we want to show that all numbers from $n$ to $A(n)$ of correct parity are $n$-squareable and know it for $n\le m-1$. Let $m\le N\le A(m)$. We should be able to find $k$ such that $m-k\le N-k^2\le A(m-k)$. Trying $k=1$, we see that we can assume $N>A(m-1)$. Then we can go up to $k=[\sqrt{A(m-1)-m+1}]=q(m)$ for sure. Thus, we can take $A(m)=A(m-k)+k^2$ with any $k$ up to $q(m)$. Let now $c^2=\liminf_{m\to\infty}m^{-2}A(m)$. Then we can take $k>am$ with any $a<c$ eventually and get $c^2\ge c^2+c^2(1-c)^2$ whence $c=1$. Well, formally I need to show that $c>0$ to claim that, but this is not hard. First, you check that $A(m)\ge 2m-1$ by replacing $1^2+1^2$ with $2^2$ a few times and then use $k$ up to $m/5$, say, as the first square and see that you can add anything from $m-k$ to $2m-2k-1$ to it and the resulting intervals overlap as long as $2k-1+m-k\le 2m-2k+1$, which is OK with $k\approx \frac m4$. Thus, eventually, you can fly to the top. However, the takeoff is pretty bumpy, and is better left to computers.

This is constructive enough, though will require "special considerations" for small $m$ (up to $50$ or so if you are aiming exactly at what you wrote).

Answer by fedja for Maximization of a certain ratio for a concave positive function

2012-11-02T02:27:56Z

Sure. Just do the most natural things.

Assume that you can have $g''<-(\frac 14+\delta)x^{-2}g(x)$ on a short interval starting at $0$ with some $\delta>0$. Note that the inequality is invariant under scalings $g(x)\mapsto ag(bx)$, so you can stretch the interval as much as you want and normalize to $g(1)=1$. Now use the compactness of concave functions normalized in such way (harnessing them with a fixed multiplicative convolution to avoid any issues with the differentiablity of the limit if you do not feel like working with generalized derivatives at the moment) and get a solution of the same differential inequality on the whole positive semi-axis.

Since you already suspect that $\sqrt x$ is the worst you can have, write $g(x)=u(x)\sqrt x$, differentiate honestly, and arrive at the inequality $$ u''+x^{-1}u'+\delta x^{-2}u\le 0\,. $$ Now rewrite it as $$ (xu')'+\delta x^{-1}u\le 0 $$ Since $u>0$, this means at the very least that $xu'$ is decreasing. If $u'$ gets negative anywhere, then you get $u'(x)\le -\frac cx$ at infinity. But then the integral of $u'$ diverges to $-\infty$, so $u$ gets negative itself somewhere, which is impossible. Thus $u'\ge 0$ all the way. But then $u\ge c$, so $(xu')'\le -\frac {\delta c}x$, whence (using the divergence of the harmonic integral again) $xu'$ tends to $-\infty$ making $u'$ eventually negative. Thus, "Kuda ne kin', vezde klin" (I surmise you understand Russian).

Of course, you can achieve $\frac{g''}g<-\frac{1}{4x^2}$ by considering $g(x)=\sqrt x-x^2$ on $(0,1)$ or something like that. So, strictly speaking, $\frac{1}{4x^2}$ is unbeatable only asymptotically, but I assume that this is what you meant from the beginning when asking the question.

I should confess that you arose my curiosity by claiming that you need a solution urgently and reviving an old post of mine to attract my attention. Normally you should understand that people visit MO in their free time and have no obligations whatsoever as to how fast to respond or whether to respond at all. So, I naturally wonder why it couldn't wait for a few hours or days :).

Comment by fedja

2013-05-06T02:21:02Z

I'm glad you mentioned geometry. I surmise that this includes distinction between shapes as abstract objects. From this point of view any tool making requiring changing the original shape counts as "an application of math." (and, surprise, crows can do that too :)). We have paleolithic tools from 2.6 million years ago. By the middle paleolithic age, the stone tools were carefully made into the desired shapes. As to Lebombo bone, I'm not sure that if you show a hacksaw or a grate to someone who has no idea what they are for, he'll not declare them counting tools. :)

Comment by fedja

2013-05-05T14:41:15Z

That depends heavily on what you mean by "mathematics". It underwent a sharp transition from the descriptive science to the deductive science sometimes somewhere in the Ancient Greece (it is believed that Thales of Miletus was the first to apply the deductive argument to a geometric problem about 600 BC but we have no proof that nobody did it earlier. Most likely, Thales just was influential enough to get it noticed and followed). This transition was so drastic and had so many implications that I would call everything that preceded it "pre-mathematics". As to mere counting, crows can do it.

Comment by fedja

2013-05-05T14:22:03Z

If you look at mathoverflow.net/questions/88640/…, you'll realize that the question you ask is far too general to have a good answer. :(

Comment by fedja

2013-05-05T00:30:36Z

The correlation is the cosine of the angle $\alpha$ between the vectors, so the question can be rephrased like this: given many vectors in a Hilbert space with some known angles, what can be said about the other angles? The particular example you mentioned is answered by the angular triangle inequality: $|\alpha(x,y)-\alpha(y,z)|\le \alpha(x,z)\le \alpha(x,y)+\alpha(y,z)$. If you know more angles, the picture gets more complicated. Another good way to look at this problem is to notice that the only restrictions on the correlation matrix are its positive definiteness and 1's on the diagonal.

Comment by fedja

2013-03-15T20:34:10Z

No chance. The twice larger balls can easily have a common point, so if you put a Dirac point mass there, you'll blow up the $L^1$-norm of $g$.

Comment by fedja

2013-03-11T17:45:29Z

Ah, I see: you just want to use the trivial $L^\infty$ bound versus the measure estimate instead of CS. You are, of course, right: this would be both obvious and useless, and this is certainly not what was meant. I apologize for not making it clearer.

Comment by fedja

2013-03-11T17:38:47Z

Erm... What have you done with the square root in Cauchy-Schwarz? I see $\int_E|f|\le\sqrt{\mu(E)\int_0^1|f|^2}$, which gives $e^{(\log 2-c)/2}$.

Comment by fedja

2013-02-20T21:30:08Z

Do you need small $n$ or only the large $n$ limit? The last one can, probably, be derived from the Brownian motion approximation where you have neat formulae for everything; the exact nature of the steps shouldn't really matter much.

Comment by fedja

2013-02-20T18:07:40Z

Yes, I can. $\phantom{}$

Comment by fedja

2013-02-20T12:23:50Z

Why don't you just read a textbook or two? Gaier's "Lectures on complex approximation" is a good one to start with.

Comment by fedja

2013-02-19T23:44:42Z

There is one thing I fail to understand: what prohibits all vectors to be (almost) the same? Then the expectation of the length is $m$, not $\sqrt m$. Of course, then the variance is $0$, so that part is OK in this trivial example.

Comment by fedja

2013-02-19T06:13:56Z

Since you have seen those "bad videos", why don't you just contact the authors directly. If you know the name and the institution, google will usually give you the e-mail and other contact information. I personally am not interested though I once offered a professional artist $1000 for a free style picture of the proof of one of the theorems in convex geometry under the condition that the artist learns all the details of the proof before painting anything. The offer was rejected and I doubt very much that an artist and a mathematician can find any common language.

Comment by fedja

2013-02-18T17:11:23Z

Unless you specify the degree of the polynomial, in which case just google "Markov's inequality".

Comment by fedja

2013-02-18T12:39:38Z

Plenty of them. $(e^x-e^{-2x})/x$ is the simplest example. As a matter of fact, every continuous function $g(x)$ on $\mathbb R$ can be approximated by an entire function with arbitrary continuous precision $\varepsilon(x)>0$. Voting to close.

Comment by fedja

2013-02-16T20:32:00Z

@Steven It can be converted to a math question, but that conversion is 80% of the fun. If you have ever talked to engineers and other applied people, you know that the starting point is to figure out what they are really after. Whether this process is "proper math." or not is a matter of opinion. I believe it is but I've heard many arguments to the contrary too...