13,282 reputation
34569
bio website
location
age
visits member for 1 year, 3 months
seen 8 hours ago

1d
comment lower-bound for $Pr[X\geq EX]$
That looks very nice! Well done!
1d
comment lower-bound for $Pr[X\geq EX]$
Right, in terms of $\alpha$ only. (I think in some ranges (either $\alpha\to 0$ or $\alpha \to 1$) one in fact gets a uniform bound even independent of $\alpha$.) Note: I don't have any real applications for this, just curiosity!
1d
comment lower-bound for $Pr[X\geq EX]$
The problem is to get lower bounds independent of $n$. From Pokrovskiy's work (which is quite involved, but gives more) I think I can do this. But maybe you can see a simpler way!
1d
comment lower-bound for $Pr[X\geq EX]$
Here's Feige's paper: wisdom.weizmann.ac.il/~feige/Others/newmarkov.pdf
1d
comment lower-bound for $Pr[X\geq EX]$
@fedja: Of course the example above, doesn't really have to do with numbers or primes. Suppose the $X_i$ are all $0$ with probability $1-\alpha$ and some value $a_i$ with probability $\alpha$. Then the expected value of $\sum X_i$ is $\alpha\sum a_i$. Estimate the probability that $\sum X_i$ is at least this expectation. A good bound for this would follow from the Manickam, Miklos, Singhi conjecture, and for certain ranges of $\alpha$ this would now follow from thework of Pokrovskiy arxiv.org/pdf/1308.2176.pdf . But perhaps I'm seeing more to this question than OP intended!
1d
comment lower-bound for $Pr[X\geq EX]$
@fedja: Good point. Here's an example of what I have in mind. Factor a square-free number $N$ as a product of primes $p_1\cdots p_n$. Now take $a_i=\log p_i/\log N$, and $X_i=0$ with probability $1-\alpha$ and $a_i$ with probability $\alpha$. Then the expected value of $\sum X_j$ is $\alpha$, and the problem is to bound a weighted sum of divisors of $N$ that are at least $N^{\alpha}$. This problem was studied by Alladi, Erdos and Vaaler and Soundararajan, and when $\alpha$ is rational there is a lower bound depending only on $\alpha$ and not on $n$.
2d
comment lower-bound for $Pr[X\geq EX]$
So I had in mind the situation that the variables are all independent. It would be good for OP to clarify if that's to be assumed or not. The situation when the variables are independent is related to problems in combinatorial number theory (studied by Alladi, Erdos and Vaaler), and to the Manickam, Miklosh and Singhi conjecture in combinatorics (on which there has been interesting progress lately).
2d
comment lower-bound for $Pr[X\geq EX]$
This is actually a non-trivial and very interesting question. It should not be closed. I'll try to add an answer with references to related work if I get a chance.
Nov
23
comment Biquadratic reciprocity for $p\equiv 1\pmod 4$ and $q\equiv 3\pmod 4$
Seva: It doesn't seem to me that $p$ is assumed to be $1\pmod 8$. When $q$ divides $a$ (which is the example you raised) then the biquadratic symbol is determined by $(\frac{2}{q})$. I'm not an exper, and it may be safest to consult Lemmermeyer's book.
Nov
23
comment Biquadratic reciprocity for $p\equiv 1\pmod 4$ and $q\equiv 3\pmod 4$
The sign doesn't matter. If you multiply $(\frac{\sigma(b+\sigma)}{q})$ and $(\frac{-\sigma(b-\sigma)}{q})$ together, you get $(\frac{-\sigma^2(b-\sigma^2)}{q}) = (\frac{a^2}{q})=1$.
Nov
23
comment Biquadratic reciprocity for $p\equiv 1\pmod 4$ and $q\equiv 3\pmod 4$
An answer is given in the wikipedia page you linked in the section under Dirichlet. If $p\equiv \sigma^2 \pmod q$ then $(\frac{-q}{p})_4=(\frac{\sigma(b+\sigma)}{q})$. A reference is given to Lemmermeyer's book.
Nov
22
comment A perfect $(n,k)$ shuffle function
If you label the cards $0$ to $n-1$ then your shuffle corresponds to multiplying card $i$ by the inverse of $k$ modulo $n-1$. Thus it returns to the original configuration in the order of $k^{-1}$ mod $n-1$ steps. But this is the same as the order of $k$ mod $n-1$.
Nov
22
comment A perfect $(n,k)$ shuffle function
Seems to be the order of $k$ mod $n-1$. (This is well known for the usual perfect outer shuffle, and seems numerically to work in your other examples.)
Nov
15
comment $\pm1$-polynomials with a maximal non-real root
Very interesting! Clearly there's something to think through there.
Nov
13
comment Bound for sums of bounded multiplicative functions that are zero at primes
The number of square-full integers up to $x$ is $O(x^{\frac 12})$.
Nov
12
comment $\pm1$-polynomials with a maximal non-real root
Interesting! I don't know what it means! You could also look at the Odlyzko-Poonen situation, and see if there is a pattern to the polynomials there that have largest non-real root. Maybe that problem will have a similar feature to what you're seeing here?
Nov
10
comment A number theoretic identity
Do those who voted to close see an easy proof of this? It seems a remarkable fact to me (if true), but maybe I'm missing something obvious. The objection that the problem is unmotivated doesn't seem correct to me: if the numbers from $1$ to $m$ are permuted randomly without fixed points, the expected value of $|a-\sigma(a)|$ would be the answer given. It's not at all clear to me why multiplication by $\lambda$ should always give exactly this answer.
Nov
9
comment $\pm1$-polynomials with a maximal non-real root
Most of the zeros of a $\pm 1$ polynomial will cluster around the unit circle, and get equidistributed in angle. So every point on the unit circle is a limit point of zeros.
Nov
9
comment A number theoretic identity
The link given by darij grinberg to a possible proof by hipsishopsis no longer works. The question doesn't look bad to me.
Nov
6
comment Largest area of a compactly supported positive definite function
The Poisson summation formula would give $\sum_{n\in {\Bbb Z}} f(n) = \sum_{k\in {\Bbb Z}} {\hat f}(k)$. The LHS is $1$, and since ${\hat f}(k)\ge 0$ by assumption, it follows that ${\hat f}(0) \le 1$.