User henry yuen - MathOverflow

A measure of closure under sumset?

2013-05-21T23:35:34Z

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 additive energy, 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|$.

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)$?

In particular, I'm mostly concerned with situations when $G$ is a vector space like $\mathbb{F}^n$ for some finite field $\mathbb{F}$.

Multivariate Hensel's Lemma, but with only one polynomial

2012-10-03T03:27:01Z

One version of Hensel's Lemma is the following statement:

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.

The multidimensional generalization of Hensel's Lemma is often presented as:

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$.

Here, $J(\alpha)$ denotes the evaluation of the Jacobian of $f_1,\ldots,f_n$ on $\alpha$.

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?

Thank you!

Entire function interpolation with control over multiplicities/derivatives

2010-05-19T08:08:27Z

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$ - p is only 1 on the $b_i$'s.

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$.

I've been thinking about doing the following:

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$.

The problem of polynomial interpolation and fitting seems very well studied; however, I can't seem to find a reference for this particular puzzle.

Thanks in advance!

Can formal power series become polynomial often, when composed with polynomials?

2012-07-27T03:53:10Z

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:

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.

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|$).

What bounds on $|C|$ can we get?

Thank you, Henry

Uniqueness of Hensel factors of a polynomial (invariant to change of "basepoint")?

2012-06-23T00:30:05Z

An important component of algorithms for factoring multivariate polynomials over a commutative ring $R$ is Hensel lifting. Here's a brief, concrete example to set the stage for my question:

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 base points. 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)$.

Hensel lifting gives an algorithmic way to lift 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 Hensel roots.

(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$).

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'$.

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?

Thank you!

Behavior of essential singularities in an 'open cone'

2011-08-04T17:30:30Z

Picard's Big Theorem 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.

Is there a version of Picard's theorem that goes something like this?

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 < \phi < 2\pi$, and define $Cone(w,V,\theta,\phi)$ to be $V \cap \lbrace w + re^{i\varphi} \mid r > 0, \theta < \varphi < \phi \rbrace$. Think of this as a "pizza slice" of the disc $V$.

Is it true that there exists an $\alpha$ such that $f(z) = \alpha$ for infinitely many $z\in Cone(w,V,\theta,\phi)$?

Inequalities and bounds for relating p-norms (Reference request)

2011-03-25T17:11:06Z

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.

Are there textbooks that go more in depth than these two?

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?

Any references or links or pointers would be greatly appreciated!

Thanks, Henry

Degenerate case of linear programming duality?

2010-12-24T16:46:08Z

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$?

Thanks!

What is the relationship between singular value decomposition and solving linear systems?

2010-11-14T07:18:10Z

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}||$.

However, is there a reverse reduction that is also very efficient? That is, if you can solve linear equations, you can solve SVD?

EDIT: Because of Denis's comment/answer below, it looks like there isn't a reduction in general. 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")?

The answer still seems to be in the negative, but I defer to people who actually know something about this.

What's known about the relationship about EQP and BQP?

2010-10-01T17:12:54Z

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.

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?

What about the relationship of EQP and P?

Answer by Henry Yuen for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T08:12:07Z

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.

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).

You can then approximate pi with $\pi r^2 /4r^2 \approx A/T$, but $r=1$, so $\pi \approx 4A/T$.

Converse of Picard's Big Theorem?

2010-09-02T05:00:20Z

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.

Now - is the converse true? Is this a way to characterize the existence of an essential singularity of a function?

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$?

Descriptive complexity theoretic-characterizations of P and NP

2010-08-09T18:31:29Z

Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material.

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$.

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?

Sum of subset of geometric series: a^2^n

2010-05-11T01:37:21Z

The formula for 1 + a + a^2 + .... where 0 < a < 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,

$S = a + a^2 + a^4 + a^8 + \cdots$

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.

Can curves induced by analytic maps wiggle infinitely across a line?

2010-04-22T06:51:05Z

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$?

We're trying to show something about analytic continuation, but we cannot rule out pathological beasts like these.

Thanks!

Comment by Henry Yuen

2013-05-22T14:26:58Z

Thanks, quid, for your answer, and the links to Hamidoune's work.

Comment by Henry Yuen

2012-10-08T18:04:01Z

I have a quick clarification question: When you say "Suppose $Q(X_1,\ldots,X_n)$ is in $I^t$", 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!

Comment by Henry Yuen

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!

Comment by Henry Yuen

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.

Comment by Henry Yuen

2011-08-13T06:35:11Z

This is an excellent lead! Thank you - I will look into these Julia lines.

Comment by Henry Yuen

2011-08-04T21:05:34Z

Thanks, of course! I have changed the question slightly, hopefully it is less trivial.

Comment by Henry Yuen

2011-03-25T18:15:05Z

I have specified that $\psi$ and $\phi$ are unit vectors in the 2 norm, however.

Comment by Henry Yuen

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.

Comment by Henry Yuen

2010-11-14T08:32:27Z

That's quite interesting. What do you mean by "one aspect of resolution"?

Comment by Henry Yuen

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!

Comment by Henry Yuen

2010-10-01T16:54:24Z

This proof works also for showing that NP is not equal to SPACE(n).

Comment by Henry Yuen

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 "syntactic characterization" (whatever that may mean formally)? That seems quite special. Well - this is all just mindsand, of course.

Comment by Henry Yuen

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.

Comment by Henry Yuen

2010-08-11T17:10:11Z

When you say, "we can diagonalize against the class to obtain a separation result..", 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?

Comment by Henry Yuen

2010-08-11T17:07:13Z

You mean, "The evidence for the former is not as dramatic as that for the latter."