User henry yuen - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:13:20Z http://mathoverflow.net/feeds/user/5534 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/131400/a-measure-of-closure-under-sumset A measure of closure under sumset? Henry Yuen 2013-05-21T23:35:34Z 2013-05-22T02:05:30Z <p>Let $G$ be an Abelian group. Let $A \subseteq G$. In additive combinatorics, one of the primary measures of the additive structure of $A$ is its <em>additive energy</em>, defined as $E(A) = |\lbrace(a_1,a_2,a_3,a_4) \in A^4 : a_1 + a_2 = a_3 + a_4 \rbrace|$. </p> <p>A related quantity that I'm interested in is: $F(A) = |\lbrace (a_1,a_2) \in A^2 : a_1 + a_2 \in A \rbrace|$. It seems to me that $F(A)$ captures the notion of "closed under sumset" more directly. How come $F(A)$ isn't studied more in additive combinatorics? What kinds of statements can one make about the relationship between $F(A)$ and $E(A)$?</p> <p>In particular, I'm mostly concerned with situations when $G$ is a vector space like $\mathbb{F}^n$ for some finite field $\mathbb{F}$.</p> http://mathoverflow.net/questions/108687/multivariate-hensels-lemma-but-with-only-one-polynomial Multivariate Hensel's Lemma, but with only one polynomial Henry Yuen 2012-10-03T03:27:01Z 2012-10-03T05:43:48Z <p>One version of Hensel's Lemma is the following statement: </p> <p>Let $R$ be a commutative ring with a unit. Given a polynomial $Q\in R[X]$ and a root $\alpha$ of $Q$ modulo some ideal $I$ (i.e. $Q(\alpha) \in I$), assuming some non-degeneracy conditions (e.g. $Q$ is square-free), then for every $t > 1$, there exists $\beta_t \in R$ such that $\beta_t = \alpha \mod I$, and $Q(\beta_t) \in I^t$, and furthermore, $\beta_t$ is unique. </p> <p>The multidimensional generalization of Hensel's Lemma is often presented as:</p> <p>Given $f_1,\ldots,f_n$ in $R[X_1,\ldots,X_n]$ and a simultaneous root $\alpha \in R^n$ modulo an ideal $I \subset R$ (i.e. $f_i(\alpha) \in I$ for all $i$), assuming some non-degeneracy conditions (e.g. $\det J(\alpha)$ is a unit), there exists $\beta_t \in R^n$ such that $\beta_{t,j} = \alpha_j \mod I$ for all $j$, and $f_i(\beta_t) \in I^t$ for all $i$.</p> <p>Here, $J(\alpha)$ denotes the evaluation of the Jacobian of $f_1,\ldots,f_n$ on $\alpha$. </p> <p>My question is: is there an intermediate generalization in between the univariate case and the multivariate case above where we only consider one polynomial $Q\in R[X_1,\ldots,X_n]$, and we simply want to lift roots of $Q$ modulo an ideal $I$ to roots of $Q$ modulo $I^t$? It seems intuitively like an easier thing to do (we don't require simultaneous solutions to a system of polynomial equations). Does this intermediate generalization exist, and if so, what non-degeneracy conditions would we require?</p> <p>Thank you!</p> http://mathoverflow.net/questions/25211/entire-function-interpolation-with-control-over-multiplicities-derivatives Entire function interpolation with control over multiplicities/derivatives Henry Yuen 2010-05-19T08:08:27Z 2012-08-12T12:34:15Z <p>Let's say I have a multiset of complex numbers $\lbrace a_1,\cdots,a_n\rbrace$ (so some of the elements may be repeated) and I would like to construct an entire function $p(z)$ with those numbers as zeroes. However, I also have a multiset of complex numbers $B = \lbrace b_1,\cdots,b_n \rbrace$ such that I wish $p(b_i) = 1$ - <b>p is only 1 on the $b_i$'s</b>. </p> <p>It seems like trying to use Lagrange's polynomial interpolation formula gives you a polynomial with too high a degree (greater than $n$ and less than or equal to $2n$), and then there's the possibility that $p^{-1}(1) \nsubseteq B$. </p> <p>I've been thinking about doing the following:</p> <p>Let $g(z) = (x-a_1) \cdots (x - a_n)$, and then via Weierstrass construct an entire function $h(z)$ such that $e^{h(b_i)} = 1/g(b_i)$. Then it seems like the entire function $e^{h(z)}g(z)$ is getting somewhat closer to what I want - but then again I don't know if there are any other $\alpha$'s such that $e^{h(\alpha)}g(\alpha) = 1$ where $\alpha \notin B$. </p> <p>The problem of polynomial interpolation and fitting seems very well studied; however, I can't seem to find a reference for this particular puzzle.</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/103265/can-formal-power-series-become-polynomial-often-when-composed-with-polynomials Can formal power series become polynomial often, when composed with polynomials? Henry Yuen 2012-07-27T03:53:10Z 2012-07-30T00:07:26Z <p>Let $F$ be a finite field. Let $F[X]$ and $F[[X]]$ denote the ring of polynomials and power series over $F$, respectively. I'm trying to show a statement like the following:</p> <p>Fix a $d > 0$. Let $g\in F[[X]]$. If there exists a set $C\subseteq F[X]$ of polynomials (with no constant term) of degree at most $k$ such that for all $c\in C$, $g(c)$ -- $g$ composed with $c$ -- is a degree $kd$ polynomial, and $|C|$ is "large" (some function of $k$, $d$, and $|F|$), then $g$ must actually be a polynomial. </p> <p>I'm trying to beat the bound that one might be able to get via Schwartz-Zippel, where $|C| > kd |F|^{k-1}$ (where $kd \ll |F|$). </p> <p>What bounds on $|C|$ can we get?</p> <p>Thank you, Henry</p> http://mathoverflow.net/questions/100413/uniqueness-of-hensel-factors-of-a-polynomial-invariant-to-change-of-basepoint Uniqueness of Hensel factors of a polynomial (invariant to change of "basepoint")? Henry Yuen 2012-06-23T00:30:05Z 2012-06-23T01:45:39Z <p>An important component of algorithms for factoring multivariate polynomials over a commutative ring $R$ is <i>Hensel lifting</i>. Here's a brief, concrete example to set the stage for my question:</p> <p>Let $f \in F[X,Y]$, where $F$ is an algebraically closed field. Suppose that for some $b\in F$, $f(b,Y)$ is square-free; call such points <i>base points</i>. Let $\alpha^{(b)}_1,\ldots,\alpha^{(b)}_n$ be roots of the univariate polynomial $f(b,Y)$, or equivalently roots of $f(X,Y)$ modulo the ideal $(X - b)$. </p> <p>Hensel lifting gives an algorithmic way to <i>lift</i> the roots $\alpha^{(b)}_i$ of $f$ modulo $(X - b)$ to roots $g^{(b)}_i$ modulo $(X-b)^t$ for any $t$, where we have the property that $g^{(b)}_i = \alpha^{(b)}_i \mod (X-b)$. Call these roots <i>Hensel roots</i>.</p> <p>(In a polynomial factorization application, there would be a way to take the $g^{(b)}_i$'s and convert them to actual factors of $f$).</p> <hr /> <p>Here's my question: given two base points $b$ and $b'$ of $f$, we've performed the Hensel lifting procedure to obtain the Hensel factors ${ g^{(b)}_i }$ and ${ g^{(b')}_i }$ (lifted to the same level). Since $F$ is algebraically closed, there are the same numbers of Hensel factors over $b$ as there are over $b'$. </p> <p>Is there any relation between $g^{(b)}_i$ and $g^{(b')}_i$ that's meaningful? Can we say that $g^{(b)}_i(X - b) = g^{(b')}_i(X - b')$? That is, are Hensel roots preserved across change of base points? </p> <p>Thank you!</p> http://mathoverflow.net/questions/72102/behavior-of-essential-singularities-in-an-open-cone Behavior of essential singularities in an 'open cone' Henry Yuen 2011-08-04T17:30:30Z 2011-08-12T17:04:43Z <p><a href="http://en.wikipedia.org/wiki/Picard_theorem" rel="nofollow">Picard's Big Theorem</a> says that if a function $f(z)$ has an isolated essential singularity at a point $w$, then in every neighborhood of $w$, $f(z)$ hits every complex number infinitely many times, with perhaps at most one exception.</p> <p>Is there a version of Picard's theorem that goes something like this?</p> <p>Let $V$ be an open disc (finite radius) such that $f(z)$ is holomorphic on $V - \lbrace w \rbrace$, and has an essential singularity at $w$. Let $0 \leq \theta &lt; \phi &lt; 2\pi$, and define $Cone(w,V,\theta,\phi)$ to be $V \cap \lbrace w + re^{i\varphi} \mid r > 0, \theta &lt; \varphi &lt; \phi \rbrace$. Think of this as a "pizza slice" of the disc $V$.</p> <p>Is it true that there exists an $\alpha$ such that $f(z) = \alpha$ for infinitely many $z\in Cone(w,V,\theta,\phi)$?</p> http://mathoverflow.net/questions/59583/inequalities-and-bounds-for-relating-p-norms-reference-request Inequalities and bounds for relating p-norms (Reference request) Henry Yuen 2011-03-25T17:11:06Z 2011-03-27T15:10:09Z <p>Hello all, I'm trying to find a good resource for a discussion on the relation between say, the p-norm of a vector (from a finite dimensional vector space) and its Euclidean norm. In my search on the internet and in various books, I only encounter basic, standard inequalities such as the Cauchy-Schwarz and Holder's inequality. </p> <p>Are there textbooks that go more in depth than these two? </p> <p>In particular, I'm interested in the following: if I have two unit vectors $\psi$ and $\phi$ (from $R^d$, say), that are $\epsilon$-close, meaning that $\|\psi - \phi\|_2 \leq \epsilon$, then what can one say about $\|\psi\|_p - \|\phi\|_p$? Intuitively, they must be close as well, but does the closeness depend on $d$, the dimension of the vector-space?</p> <p>Any references or links or pointers would be greatly appreciated!</p> <p>Thanks, Henry</p> http://mathoverflow.net/questions/50291/degenerate-case-of-linear-programming-duality Degenerate case of linear programming duality? Henry Yuen 2010-12-24T16:46:08Z 2010-12-27T10:43:11Z <p>Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize $0\vec{y}$, subject to $\vec{y}\matrix{A}\geq\vec{c}, \vec{y}\geq 0$". I'm particularly bothered by the "minimize $0$" part of the dual program - but does the duality theorem still hold - that is: is it true that if there is a $\vec{y}$ that is feasible for the dual program, then for all $\vec{x}$ that is feasible for the primal program, $\vec{c}\vec{x} \leq 0$?</p> <p>Thanks!</p> http://mathoverflow.net/questions/46024/what-is-the-relationship-between-singular-value-decomposition-and-solving-linear What is the relationship between singular value decomposition and solving linear systems? Henry Yuen 2010-11-14T07:18:10Z 2010-11-14T08:35:41Z <p>It is known that solving systems of linear equations is reducible to SVD in a straightforward way; if you want to solve $\mathbf{Ax}=\mathbf{b}$, then you can perform SVD on $\mathbf{A}$ and minimize $||\mathbf{UDVx}-\mathbf{b}||$. </p> <p>However, is there a reverse reduction that is also very efficient? That is, if you can solve linear equations, you can solve SVD?</p> <p>EDIT: Because of Denis's comment/answer below, it looks like there isn't a reduction <i>in general</i>. But I'm interested in these problems over $\mathbb{C}$; so, the new question is: If we can solve linear equations over $\mathbb{C}$ exactly or approximately, can we perform an "approximate" SVD (for some suitable notion of "approximate")?</p> <p>The answer still seems to be in the negative, but I defer to people who actually know something about this.</p> http://mathoverflow.net/questions/40776/whats-known-about-the-relationship-about-eqp-and-bqp What's known about the relationship about EQP and BQP? Henry Yuen 2010-10-01T17:12:54Z 2010-10-09T17:14:21Z <p>EQP is the class of problems solvable deterministically using a quantum computer in polynomial time - that seems to me to be a good analogue to P, whereas BQP is the quantum analogue of BPP. </p> <p>It doesn't seem like much is known about EQP! Just like BPP is not known to be contained in NP, is it known whether EQP \subseteq BQP \subseteq QMA? Is there a corresponding "Derandomization" of BQP into EQP? </p> <p>What about the relationship of EQP and P?</p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38279#38279 Answer by Henry Yuen for What is the easiest randomized algorithm to motivate to the layperson? Henry Yuen 2010-09-10T08:12:07Z 2010-09-10T08:12:07Z <p>I love the following example: approximating pi. Ask a person to come up with a relatively efficient algorithm to compute the digits of pi, and unless they already know some math, most will draw a blank. </p> <p>Here's something that anybody with a basic geometry background will understand: Simply generate many random 2D points (x,y) in the box [-1,1]x[-1,1], and count the number of points within distance 1 of 0 (call this number A) and the number of points in the box total (call this number T).</p> <p>You can then approximate pi with $\pi r^2 /4r^2 \approx A/T$, but $r=1$, so $\pi \approx 4A/T$. </p> http://mathoverflow.net/questions/37458/converse-of-picards-big-theorem Converse of Picard's Big Theorem? Henry Yuen 2010-09-02T05:00:20Z 2010-09-02T05:16:11Z <p>The celebrated Big Theorem of Picard's is that, in every open set containing an essential singularity of a function $f(z)$, $f(z)$ takes on every value (except for at most one) of $\mathbb{C}$ infinitely often.</p> <p>Now - is the converse true? Is this a way to characterize the existence of an essential singularity of a function? </p> <p>For example, if you're given a non-constant function $f(z)$ that is holomorphic on some open set $\Omega$, and you know that there is an accumulation of 0's towards some point $x$ on the boundary of $\Omega$, then do you know that there must be an essential singularity at $x$? </p> http://mathoverflow.net/questions/35032/descriptive-complexity-theoretic-characterizations-of-p-and-np Descriptive complexity theoretic-characterizations of P and NP Henry Yuen 2010-08-09T18:31:29Z 2010-08-09T21:19:37Z <p>Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material. </p> <p>The major successes of Descriptive Complexity include Fagin's result that $NP=SO\exists$ (that is, the class NP is equal to the class of models of a second-order existential query over some vocabulary), and also that $P = FO(LFP)$ (that the class P is equal to the class of models of first-order queries that might use a Least-Fixed-Point operator), and also $PH = SO$.</p> <p>My understanding of mathematical logic is quite shaky, but from what I understand, second-order formulas are not expressible in first order logic - how does this fact stand in relation to the results I mentioned above? Why does it not separate NP from P, or PH from P? </p> http://mathoverflow.net/questions/24190/sum-of-subset-of-geometric-series-a2n Sum of subset of geometric series: a^2^n Henry Yuen 2010-05-11T01:37:21Z 2010-05-11T02:55:19Z <p>The formula for 1 + a + a^2 + .... where 0 &lt; a &lt; 1 is $\frac{1}{1-a}$, but what if you wanted to sum only those where the exponent is a power of 2? That is,</p> <p>$S = a + a^2 + a^4 + a^8 + \cdots$ </p> <p>I feel like this is an easy one but I just can't seem to find a closed expression for it, nor search for it on Google. </p> http://mathoverflow.net/questions/22154/can-curves-induced-by-analytic-maps-wiggle-infinitely-across-a-line Can curves induced by analytic maps wiggle infinitely across a line? Henry Yuen 2010-04-22T06:51:05Z 2010-04-22T07:26:27Z <p>Let $f$ be a function analytic on an open subset $D\subset \mathbb{C}$, and let $\gamma:[0,1] \to D$ be a line segment. $g = f\circ\gamma$ is another curve in the complex plane; is it possible to for $g$ to cross a straight line infinitely often, where the crossing points accumulate towards a point? That is, does there exist a point $\alpha$ and a ray $R$ emanating from the point $\alpha$ such that for all $\epsilon > 0$, $g$ crosses the ray $R$ infinitely many times in the $\epsilon$-ball around $\alpha$?</p> <p>We're trying to show something about analytic continuation, but we cannot rule out pathological beasts like these.</p> <p>Thanks!</p> http://mathoverflow.net/questions/131400/a-measure-of-closure-under-sumset/131402#131402 Comment by Henry Yuen Henry Yuen 2013-05-22T14:26:58Z 2013-05-22T14:26:58Z Thanks, quid, for your answer, and the links to Hamidoune's work. http://mathoverflow.net/questions/108687/multivariate-hensels-lemma-but-with-only-one-polynomial/108691#108691 Comment by Henry Yuen Henry Yuen 2012-10-08T18:04:01Z 2012-10-08T18:04:01Z I have a quick clarification question: When you say &quot;Suppose $Q(X_1,\ldots,X_n)$ is in $I^t$&quot;, you mean suppose there is are $\beta_1,\ldots,\beta_n\in R$ such that $Q(\beta_1,\ldots,\beta_n)\in I^t$? And then every time you write $\frac{dQ}{dX_1}$, you mean it is evaluated at the $\beta_1,\ldots,\beta_n$? If that's the case, then I interpret the mod $I^{t+1}$ solution as $\beta_1 + a_1,\ldots,\beta_n+a_n$. Thanks! http://mathoverflow.net/questions/103265/can-formal-power-series-become-polynomial-often-when-composed-with-polynomials/103484#103484 Comment by Henry Yuen Henry Yuen 2012-07-30T14:37:59Z 2012-07-30T14:37:59Z Thanks David! This will take me a little while to parse, so i might add follow up questions in the comments. But for now I accept this! http://mathoverflow.net/questions/103265/can-formal-power-series-become-polynomial-often-when-composed-with-polynomials Comment by Henry Yuen Henry Yuen 2012-07-27T04:50:47Z 2012-07-27T04:50:47Z Thanks for pointing this out Ryan. In this case, I have a specific $d$ in mind: if $g(c)$ has degree greater than $kd$, then I do not wish to consider such a $c$. The bound I'm seeking on $|C|$ may depend on $d$. I will edit the problem statement to make this clearer. http://mathoverflow.net/questions/72102/behavior-of-essential-singularities-in-an-open-cone/72774#72774 Comment by Henry Yuen Henry Yuen 2011-08-13T06:35:11Z 2011-08-13T06:35:11Z This is an excellent lead! Thank you - I will look into these Julia lines. http://mathoverflow.net/questions/72102/behavior-of-essential-singularities-in-an-open-cone/72104#72104 Comment by Henry Yuen Henry Yuen 2011-08-04T21:05:34Z 2011-08-04T21:05:34Z Thanks, of course! I have changed the question slightly, hopefully it is less trivial. http://mathoverflow.net/questions/59583/inequalities-and-bounds-for-relating-p-norms-reference-request/59587#59587 Comment by Henry Yuen Henry Yuen 2011-03-25T18:15:05Z 2011-03-25T18:15:05Z I have specified that $\psi$ and $\phi$ are unit vectors in the 2 norm, however. http://mathoverflow.net/questions/19987/math-paper-authors-order/19996#19996 Comment by Henry Yuen Henry Yuen 2010-11-25T08:06:41Z 2010-11-25T08:06:41Z From Adleman himself, his role in the trio was to crack the plethora of schemes that Rivest and Shamir would come up with; it was only on the 43rd (or so) try that Adleman announced that maybe that had come up with something. But Adleman was not particularly interested in cryptography at the time, and insisted that his name go last. http://mathoverflow.net/questions/46024/what-is-the-relationship-between-singular-value-decomposition-and-solving-linear/46026#46026 Comment by Henry Yuen Henry Yuen 2010-11-14T08:32:27Z 2010-11-14T08:32:27Z That's quite interesting. What do you mean by &quot;one aspect of resolution&quot;? http://mathoverflow.net/questions/40776/whats-known-about-the-relationship-about-eqp-and-bqp/40787#40787 Comment by Henry Yuen Henry Yuen 2010-10-02T05:29:44Z 2010-10-02T05:29:44Z Thanks, Scott, for your answer! However, what did you mean by the MAJORITY function with the promised (1/3,2/3) gap? Computing this function is not in EQP relative to an oracle? If you know of the reference, that would be wonderful! http://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-other/40771#40771 Comment by Henry Yuen Henry Yuen 2010-10-01T16:54:24Z 2010-10-01T16:54:24Z This proof works also for showing that NP is not equal to SPACE(n). http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma/35284#35284 Comment by Henry Yuen Henry Yuen 2010-08-12T06:14:05Z 2010-08-12T06:14:05Z Artem, I don't understand why it would imply derandomization either, but as Ryan Williams said, it would be a very cool thing to prove. In my view, having that sort of thing would mean, informally, that all roads lead to derandomization of BPP, or that BPP is bound to be derandomized. Not only are some reasonable circuit lower bounds conditions for derandomization, but also the property of having a &quot;syntactic characterization&quot; (whatever that may mean formally)? That seems quite special. Well - this is all just mindsand, of course. http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma Comment by Henry Yuen Henry Yuen 2010-08-11T17:14:11Z 2010-08-11T17:14:11Z Also, this is not a real answer, but using reasonable complexity assumptions, BPP = P (the result due to Implagiazzo and Wigderson), of course BPP would then be a syntactic class. What would be interesting would be to show that finding a syntactic characterization of BPP would imply derandomization of BPP. http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma Comment by Henry Yuen Henry Yuen 2010-08-11T17:10:11Z 2010-08-11T17:10:11Z When you say, &quot;we can diagonalize against the class to obtain a separation result..&quot;, please clarify. I know we can diagonalize against the class TIME(f(n)) to separate TIME(f) from TIME(g) where g = $\omega(f)$ (up to logarithmic terms), but is there such a diagonalization we can use against P to separate it from something else? http://mathoverflow.net/questions/35151/what-impact-would-pnp-have-on-the-characterization-of-bqp/35185#35185 Comment by Henry Yuen Henry Yuen 2010-08-11T17:07:13Z 2010-08-11T17:07:13Z You mean, &quot;The evidence for the former is not as dramatic as that for the latter.&quot;