most recent 30 from http://mathoverflow.net 2013-05-19T13:09:36Z http://mathoverflow.net/feeds/user/3343 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120545/compute-roots-of-sum-i-c-i-a-i-b-i-xp Emanuele Viola 2013-02-01T20:28:19Z 2013-02-01T20:56:48Z

<p>How to compute the (real) roots of</p> <p>$$\sum_{i=1}^n \frac{c_i}{(a_i + b_i \cdot x)^p}$$</p> <p>for given reals $a_i, b_i, c_i$, and positive integers $n, p$? The cases $p=1, ..., 5$ and $n=6, ..., 20$ would already be very useful for me. I actually just need any root in a given interval.</p> <p>Multiplying by the denominators, this task can be reduced to finding roots of a polynomial, but this only works for very small $n$ whereas even for $n=8$ the coefficients in the polynomial are numerically unstable.</p> <p>The only other method I could think of is using binary search (aka the bisection method). But this is too slow. Is there a faster method that is numerically stable?</p>

http://mathoverflow.net/questions/117759/streamlined-probability-measure-for-tossing-infinitely-many-coins Emanuele Viola 2012-12-31T21:52:44Z 2012-12-31T22:25:04Z

<p>The standard probability measure over countably many independent coin tosses (i.e., the probability that you get a prescribed prefix of length $v$ is $2^{-v}$) is usually obtained via results in measure theory (at least, that's what I have seen). Is there a streamlined presentation out there that uses the least possible amount of results from measure theory (ideally, none) to show that this is indeed a valid probability measure?</p>

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry Emanuele Viola 2012-06-17T13:36:09Z 2012-06-20T20:11:29Z

<p>Given two expressions A and B involving integers, $\pi$, powers to rational exponents, and cosine, is there a software that determines if A = B? (Previous question asked A > B, but the bottleneck is equality.)</p> <p>I am aware of the long-standing <a href="http://maven.smith.edu/~orourke/TOPP/P33.html" rel="nofollow">sum-of-square-roots</a> problem in complexity theory. I am asking if there is a software implementation of a sound algorithm, which may take a long time or even not always terminate. As far as I know, standard math software, even if symbolic, resorts to decimal expansion to determine if A > B; but without mathematical guarantee.</p>

http://mathoverflow.net/questions/39156/asymptotics-of-packing Emanuele Viola 2010-09-17T22:08:15Z 2010-09-17T23:39:06Z

<p>Define $m(n,k,l)$ as the maximal size of a family $k$-element subsets of $[n]$ having the property that the intersection of every two sets is less than $l$.</p> <p>As stated on wikipedia, in 1985 Rödl proved Erdős’s conjecture that for fixed $k$ and $l$ $$ \lim_{n \to \infty} m(n,k,l) = \binom{n}{l}/\binom{k}{l}.$$</p> <p>(The book "the probabilistic method" contains a proof of this fact.)</p> <p>Does anybody know what happens when $k = k(n), l = l(n)$? I am especially interested in the case when $l = O(\log n)$ and $k = n^{\epsilon}$ (which is one of the settings that has applications in theoretical computer science for Nisan-Wigderson pseudorandom generators).</p>

http://mathoverflow.net/questions/12154/local-view-of-setting-pn-out-of-n-bits-to-1 Emanuele Viola 2010-01-17T23:25:00Z 2010-01-18T17:19:23Z

<p>For p a constant in (0,1) and n going to infinity such that pn is an integer, consider the distribution on n bits that selects a random subset of pn bits, sets those to 1, and sets the others to 0. What is the largest k = k(n,p) so that the induced distribution on any k bits is 1/10 close in total variation distance (a.k.a. statistical distance) to the distribution that sets each bit to 1 independently with probability p? For every p I would like to know k up to a sublinear (i.e. o(n)) additive term. (For starters, p = 1/8 is good too.) Does anybody know of a place where this is worked out?</p> <p>Thanks! Emanuele</p>

http://mathoverflow.net/questions/120545/compute-roots-of-sum-i-c-i-a-i-b-i-xp/120547#120547 Emanuele Viola 2013-02-19T14:48:57Z 2013-02-19T14:48:57Z

Thanks for the useful pointer. I wonder if something like that can be done for $p &gt; 1$?

http://mathoverflow.net/questions/120545/compute-roots-of-sum-i-c-i-a-i-b-i-xp Emanuele Viola 2013-02-01T21:49:17Z 2013-02-01T21:49:17Z

Thanks. I have not tried it because I was not sure what starting point to choose/whether the method would work in general. Do you see it?

http://mathoverflow.net/questions/120545/compute-roots-of-sum-i-c-i-a-i-b-i-xp Emanuele Viola 2013-02-01T20:48:07Z 2013-02-01T20:48:07Z

Sorry, I had set $c_i = 1$ to simplify the question. I have now put it back in so there may be roots even for even $p$.

http://mathoverflow.net/questions/117759/streamlined-probability-measure-for-tossing-infinitely-many-coins/117761#117761 Emanuele Viola 2013-01-02T14:01:40Z 2013-01-02T14:01:40Z

Thanks, but I was hoping for something more basic. Real numbers are even more difficult than infinite coin tosses, in my opinion. How would you explain this probability measure to a high-school student?

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry/99869#99869 Emanuele Viola 2012-06-20T19:03:05Z 2012-06-20T19:03:05Z

Thanks! This seems to solve basically what I asked, except I guess you can only handle integer exponents this way? It is also not hard to implement. If you make it an answer I'll accept it.

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry/99869#99869 Emanuele Viola 2012-06-19T14:22:09Z 2012-06-19T14:22:09Z

Thanks, but my question still stands. One can obtain a zero-error &quot;testeq&quot; by trying all random choices. Is this available somewhere? Also, I think this all boils down to bounding the distance from 0 of non-zero expressions -- are there bounds available for expressions involving cos/sin and powers? I am aware of Baker's work on logarithmic forms.

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry/99869#99869 Emanuele Viola 2012-06-18T13:41:36Z 2012-06-18T13:41:36Z

Thanks, this looks useful. Is there an implementation of testeq that is always correct but may take a long time?

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry/99842#99842 Emanuele Viola 2012-06-17T19:54:13Z 2012-06-17T19:54:13Z

I meant Signum, not signum.

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry Emanuele Viola 2012-06-17T18:46:56Z 2012-06-17T18:46:56Z

Input: cos(0) = cos(0.0000000000000000001) Answer: TRUE ;-)

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry/99842#99842 Emanuele Viola 2012-06-17T18:17:48Z 2012-06-17T18:17:48Z

I just tried evalr(signum(cos(1/2)^2 + sin(1/2)^2 - 1) and I got FAIL -- even with Digits := 2000; Is there a way to solve exactly this? Do you know if this would work with MetiTarski? My problems are quadratic polynomials in cos/sin in Pi (a/b) for integers a, b.

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry Emanuele Viola 2012-06-17T14:32:04Z 2012-06-17T14:32:04Z

I do need to decide exact equality. I didn't know about the conjecture you mention, and I am editing my question to clarify. Still, is there a sound algorithm which may work on specific instances?

http://mathoverflow.net/questions/99840/software-to-decide-equality-between-expressions-involving-powers-and-trigonometry/99842#99842 Emanuele Viola 2012-06-17T14:21:26Z 2012-06-17T14:21:26Z

Thank you for the pointers! Could you please elaborate on how to solve such problems in Maple? Maple would be much more convenient for me, as I don't need variables or boolean logic which may make MetiTarski a bit too complicated.

http://mathoverflow.net/questions/12154/local-view-of-setting-pn-out-of-n-bits-to-1/12210#12210 Emanuele Viola 2010-01-22T23:37:09Z 2010-01-22T23:37:09Z

I haven't verified if this works (partially because the statement of the Berry–Esseen's bound for the hypergeometric distribution looks a bit scary to me) but I am accepting Douglas' answer because the combination of the observations in the comments should indeed answer my original question. Thanks!

http://mathoverflow.net/questions/12154/local-view-of-setting-pn-out-of-n-bits-to-1/12210#12210 Emanuele Viola 2010-01-19T19:08:13Z 2010-01-19T19:08:13Z

@Douglas: Indeed I'd prefer to have k up to o(n), but I was slow at understanding the details of your answer. So you are saying the points where the hypergeometric is larger than the binomial are always an interval (seems like what Ryan was asking too), so we just apply the bound in your second reference to that interval. That makes sense. Is it easy to verify this interval property?

http://mathoverflow.net/questions/12154/local-view-of-setting-pn-out-of-n-bits-to-1/12210#12210 Emanuele Viola 2010-01-18T22:26:37Z 2010-01-18T22:26:37Z

Thanks a lot for the reference! Indeed that's very relevant. In fact I was hoping to get a tight bound on k as a function of both p and the error (now set to 1/10). The paper by Diaconis and Freedman gets close enough by giving reasonable constants. Maybe doing better than that is painful, so I'll accept your answer. Regarding your other question, I agree that's a possible approach but doesn't look easy to me.