User max alekseyev - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T16:07:54Z http://mathoverflow.net/feeds/user/7076 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27107/transforming-a-diophantine-equation-to-an-elliptic-curve/29981#29981 Answer by Max Alekseyev for Transforming a Diophantine equation to an elliptic curve Max Alekseyev 2010-06-29T23:29:23Z 2013-05-03T13:03:54Z <p>Allan MacLeod's website <a href="http://web.archive.org/web/20110305072539/http://maths.paisley.ac.uk/allanm/ECRNT/Ecrnt.htm" rel="nofollow">Elliptic Curves in Recreational Number Theory</a> considers this problem among many other interesting ones.</p> http://mathoverflow.net/questions/123062/transformation-of-a-bivariate-polynomial-into-a-homogeneous-one Transformation of a bivariate polynomial into a homogeneous one Max Alekseyev 2013-02-27T02:35:34Z 2013-03-13T11:22:00Z <p>For a given a bivariate polynomial $P(x,y)$ with rational coefficients:</p> <p><strong>Q1</strong>. How compute such (invertible) substitutions of its variables that would transform the polynomial into a homogeneous one? In particular, how to represent $P(x,x)$ as in the form $H(S(x,y),T(x,y))$, if such representation exists, where $H,S,T$ are polynomials and $H$ is homogeneous.</p> <p><strong>Q2</strong>. Can the degree of $H$ be minimized? Can maximum degree of $H,S,T$ be minimized?</p> <p><strong>Example</strong>. The polynomial $$x^6 + x^5 + (y - 6)x^4 - 3x^3 + (-y + 12)x^2 + (3y^2 + 4)x + y^3 + 4y - 8$$ can be represented as $$u^3 + uv^2 + v^3,$$ where $u=x+y$ and $v=x^2-2$.</p> <p>P.S. Trivial representation with $H(u,v)=u$ and $u=P(x,y)$, $v=0$ is unacceptable as non-invertible.</p> <p>The above questions and restrictions may sound too vague, so I'd be thankful if someone can help me to formalize the problem I'm trying to pose.</p> http://mathoverflow.net/questions/123058/expression-for-the-sum-of-square-roots-of-zeros-of-a-polynomial Expression for the sum of square roots of zeros of a polynomial Max Alekseyev 2013-02-27T01:56:52Z 2013-03-11T22:58:19Z <p>Let $f(x)$ be a polynomial of degree $n$ with rational coefficients whose zeroes are nonnegative real numbers: $x_1, \dots, x_n\geq 0$.</p> <p><strong>General question</strong>. Does there exist a simple expression for the number $$r=\sqrt{x_1} + \sqrt{x_2} + \dots + \sqrt{x_n}$$ in terms of coefficients of $f(x)$ ?</p> <p><strong>Remark</strong>. Let $s_k = x_1^k + x_2^k + \dots + x_n^k$ be the sum of $k$-th powers of zeros of $f(x)$. It is clear that for <em>nonnegative integer</em> $k$, $s_k$ can be expressed as a polynomial of the coefficients of $f(x)$ (cf. Newton-Girard formulae). The number $r$ (and even its square $r^2$) represent a zero of a polynomial whose coefficients are polynomials in $s_k$:</p> <p>$n=1:\qquad r^2 - s_1 = 0$</p> <p>$n=2:\qquad r^4 - 2 s_1 r^2 + (2 s_2 - s_1^2) = 0$</p> <p>$n=3:\qquad 3 r^8 - 12 s_1 r^6 + (6 s_1^2 + 12 s_2) r^4 + (- 20 s_1^3 + 72 s_1 s_2 - 64 s_3) r^2 + (3 s_1^4 - 12 s_1^2 s_2 + 12 s_2^2) = 0$</p> <p>$n=4:\qquad 9 r^{16} - 72 s_1 r^{14} + (180 s_1^2 + 72 s_2) r^{12} + \dots = 0$</p> <p>Unfortunately the degree of these polynomials grows as $2^n$, and in general it seems it cannot be made much smaller.</p> <p><strong>Specific question</strong>. Now, let us consider a special case of $f(x)$ satisfying the identity $f(y^2)=g(y)\cdot g(-y)$ where $g(y)$ is a polynomial with rational coefficients. Then each $\sqrt{x_i}$ is a zero of either $g(y)$ or $g(-y)$. Can we find a simple expression for $r$ in this case?</p> http://mathoverflow.net/questions/121557/like-diophantine-equation/123465#123465 Answer by Max Alekseyev for Like Diophantine equation Max Alekseyev 2013-03-03T08:28:07Z 2013-03-03T08:28:07Z <p>The equation $x^n - ny^x - nxy = 0$ has no solutions in positive integers. </p> <p>First notice that $ny$ must divide $x^n$, and $x$ in turn must divide $ny^x$. Therefore, the set of prime divisors of $x$ and $ny$ is the same.</p> <p>Let $p$ be any prime dividing $x$ (or $ny$) and $u=\nu_p(x)$, $v=\nu_p(y)$, $w=\nu_p(n)$ be the corresponding $p$-adic valuations. We remark that $u>0$.</p> <p>Since $x^n - ny^x - nxy = 0$, the two smallest values among $\nu_p(x^n)=nu$, $\nu_p(ny^x)=xv+w$, $\nu_p(nxy)=u+v+w$ must be equal. It is easy to see that $u+v+w &lt; xv+w$ unless $v=0$. So there are two cases to consider:</p> <p>1) $v=0$. In this case we have $xv+w = w &lt; u+v+w$ and $xv+w = w &lt; p^w \leq nu$, that is $\nu_p(ny^x)$ is a sole smallest valuation among the three, which is impossible.</p> <p>2) $v>0$ and $u+v+w = nu$, that is, $v+w=(n-1)u$ and thus $\nu_p(ny) = \nu_p(x^{n-1})$. Since $p$ is arbitrary prime dividing $x$ and $ny$, we conclude that $ny = x^{n-1}$. The equation take form: $$x^n - x^{n-1}y^{x-1} - x^n = 0$$ which reduces to $$x^{n-1}y^{x-1} = 0,$$ a contradiction.</p> http://mathoverflow.net/questions/123459/when-adding-a-constant-makes-a-multivariate-polynomial-reducible When adding a constant makes a multivariate polynomial reducible? Max Alekseyev 2013-03-03T05:23:46Z 2013-03-03T05:23:46Z <p>Given a multivariate polynomial $f(x_1,\dots,x_n)$ with integer coefficients, how to find an integer $m$ (if it exists) such that $f(x_1,\dots,x_n) + m$ factors into polynomials of smaller degrees? </p> <p>Are there any simple criteria to identify cases when such $m$ does not exist?</p> <p>Is it possible that more than one suitable values of $m$ exist?</p> http://mathoverflow.net/questions/120963/a-formula-combining-euler-phi-and-gcd/123408#123408 Answer by Max Alekseyev for A formula combining Euler $\phi$ and $\gcd$ Max Alekseyev 2013-03-02T12:41:07Z 2013-03-02T12:48:23Z <p>Below I characterize set of values achievable by $\psi(a_1,\dots,a_n;N)$.</p> <p>Let $d_i=\gcd(a_1,\dots,a_i+1,\dots,a_n,N)$. First notice that $d_1,\dots,d_n$ are divisors of $N$ and they are pairwise co-prime (as $d_i|(a_i+1)$ while $d_j|a_i$ for every $j\ne i$). </p> <p>I claim that besides these two conditions the values $d_i$ can be arbitrary. That is, let $d_1,\dots,d_n$ be any pairwise co-prime divisors of $N$; then there exist $a_1, \dots, a_n$ such that $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$ and thus $$\psi(a_1,\dots,a_n;N) = \sum_{i=1}^n \phi(d_i).$$</p> <p>Let $d_0=1$. Then there exist pairwise co-prime positive integers $D_0, D_1, \dots, D_n$ such that $D_0D_1\cdots D_n=N$ and $d_i|D_i$ for every $i=0,1,\dots,n$. Namely, let $D_i = \gcd(N,d_i^\infty)=\lim_{k\to\infty}\gcd(N,d_i^k)$ for every $i=1,\dots,n$; and $D_0 = \tfrac{N}{D_1D_2\cdots D_n}$.</p> <p>To enforce equalities $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$ for every $i=1,\dots,n$, it is enough to require the following congruences $$(\star)\qquad a_i \equiv d_j - \delta_{ij} \pmod{D_j}$$ for every $j=0,1,\dots,n$ (where $\delta_{ij}$ is Kronecker's delta). Indeed, if $a_1,\dots,a_n$ satisfy congruences $(\star)$, then $\gcd(a_j,D_j)=1$ and $\gcd(a_j+1,D_j)=d_j$ for $j=1,\dots,n$; and $\gcd(a_i,D_j)=d_j$ for every $i=1,\dots,n$, $j=0,\dots,n$ and $i\ne j$. So we trivially have $\gcd(a_1,\dots,a_i+1,\dots,a_n,D_i)=d_i$ while $\gcd(a_1,\dots,a_i+1,\dots,a_n,D_j)=1$ for every $j\ne i$, which further imply that $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$ for every $i=1,\dots,n$.</p> <p>For every fixed $i$, the congruences $(\star)$ represent a system of congruences for $a_i$ with pairwise co-prime moduli $D_0, \dots, D_n$. By Chinese Remainder Theorem, this system has a solution (i.e., value of $a_i$) modulo $D_0D_1\cdots D_n=N$. That is, there exist integers $a_1,\dots,a_n$ with $0\leq a_i http://mathoverflow.net/questions/123122/when-polynomial-fx2-can-be-factored-as-gxg-x When polynomial f(x^2) can be factored as g(x)·g(-x) ? Max Alekseyev 2013-02-27T17:45:46Z 2013-02-27T21:20:10Z <p>In relation to my question <a href="http://mathoverflow.net/questions/123058/expression-for-the-sum-of-square-roots-of-zeros-of-a-polynomial" rel="nofollow">http://mathoverflow.net/questions/123058/expression-for-the-sum-of-square-roots-of-zeros-of-a-polynomial</a></p> <p>How to characterize polynomials$f(x)$with rational coefficients such that$f(x^2)=g(x)\cdot g(-x)$where$g(x)$is also a polynomial with rational coefficients? </p> <p>Is there a computationally efficient way to identify if given polynomial$f(x)$is such without factoring$f(x^2)$?</p> http://mathoverflow.net/questions/31912/hexagonal-triangular-squares/31922#31922 Answer by Max Alekseyev for Hexagonal Triangular Squares Max Alekseyev 2010-07-14T23:07:13Z 2013-02-27T01:08:40Z <p>The question is equivalent to the system of quadratic Diophantine equations: $$8 n^2 = m'^2 - 1$$ $$4n^2 = 3p'^2 + 1$$ where$m'=2m+1$and$p'=2p+1$. How to solve such systems is described in my paper: <a href="http://arxiv.org/abs/1002.1679" rel="nofollow">http://arxiv.org/abs/1002.1679</a> (see Theorem 6)</p> <p>It is easy to obtain that the only nonegative solution is$n=1$,$m=1$,$p=0$.</p> http://mathoverflow.net/questions/122411/almost-converses-to-the-am-gm-inequality/122444#122444 Answer by Max Alekseyev for Almost-converses to the AM-GM inequality Max Alekseyev 2013-02-20T19:40:41Z 2013-02-21T15:44:12Z <p>Power mean inequality can give many bounds for the difference between AM and GM. Most simple is $$AM - GM \leq \max_i a_i - \min_i a_i.$$ Another bound is $$AM - GM \leq AM - HM = \frac{a_1+\dots+a_n}{n} - \frac{n}{1/a_1 + \dots + 1/a_n}$$ etc.</p> <p>See <a href="http://en.wikipedia.org/wiki/Generalized_mean#Generalized_mean_inequality" rel="nofollow">http://en.wikipedia.org/wiki/Generalized_mean#Generalized_mean_inequality</a></p> http://mathoverflow.net/questions/122427/formula-for-finite-sum/122441#122441 Answer by Max Alekseyev for Formula for finite sum Max Alekseyev 2013-02-20T19:28:20Z 2013-02-20T19:28:20Z <p>For a fixed$k$, different sets of alphas form all different$\tbinom{n}{k}$combinations of size$k$in the set$\{1,2,\dots,n\}$. Each element$j$of this set appears in exactly$\tbinom{n-1}{k-1}$such combinations. So the sum for a fixed$k$is $$\frac{1}{k} \sum_{j=1}^n \binom{n-1}{k-1}\cdot j = \frac{n+1}{2}\cdot \binom{n}{k}.$$</p> http://mathoverflow.net/questions/25955/np-complete-for-range-sum-constraints/29980#29980 Answer by Max Alekseyev for NP Complete for range sum constraints? Max Alekseyev 2010-06-29T23:15:53Z 2013-02-12T17:35:28Z <p>The problem is equivalent to checking whether the vector$(h_1,\dots,h_m)$belong to the integer <em>lattice</em> $$\{ Ax \mid x\in \mathbb{Z}^n \}$$ where$A$is a given$m\times n$integer matrix. This problem is known to belong to$P$.</p> <p>However, there exists a similar problem that is indeed$NP$-complete - namely, checking whether a given vector belongs to the integer <em>cone</em> $$\{ Ax \mid x\in \mathbb{Z}_+^n \}.$$</p> <p>The crucial difference is that in the first problem variables$x_1,\dots,x_n$can be <em>arbitrary</em> integers, while in the second problem they have to be <em>nonnegative</em> integers. And this nonnegativity requirement turns a polynomial-time problem into an$NP$-complete one.</p> http://mathoverflow.net/questions/121488/a-sum-involving-modn-arithmetic/121599#121599 Answer by Max Alekseyev for A sum involving mod(n) arithmetic Max Alekseyev 2013-02-12T13:48:26Z 2013-02-12T13:56:45Z <p>I believe the formula$|A|=\frac{\varphi(q)}{\mathrm{lcm}(\varphi(d_1),\varphi(d_2))}$is not quite correct. In particular, for$q=15$,$d_1 = 3$,$d_2=5$,$a=1$, this formula gives$|A|=2$, while, in fact,$A = \{ (1,1) \}$with$|A|=1$. Below I derive a correct formula.</p> <p>First, it is clear that if$a\not\equiv1\pmod{\gcd(d_1,d_2)}$, then$|A|=0$. For the rest assume that$a\equiv1\pmod{\gcd(d_1,d_2)}$.</p> <p>Let$p$be a prime dividing$q$and$t=\nu_p(q)>0$(i.e.,$t$is the valuation of$q$w.r.t.$p$) and$s_1 = \nu_p(d_1)$,$s_2 = \nu_p(d_2)$. It is easy to see that the number of elements modulo$p^t$in$A$is indeed $$\frac{\varphi(p^t)}{\mathrm{lcm}(\varphi(p^{s_1}),\varphi(p^{s_2}))} = \begin{cases} (p-1)p^{t-1},&amp; \text{if}\ s_1=s_2=0\\ p^{t-\max\{s_1,s_2\}},&amp;\text{otherwise}. \end{cases}$$</p> <p>Now, for any$a$such that$\gcd(a,q)=1$and$a\equiv1\pmod{\gcd(d_1,d_2)}$, we have (thanks to CRT) $$|A| = \prod_{p|q} \frac{\varphi(p^{\nu_p(q)})}{\mathrm{lcm}(\varphi(p^{\nu_p(d_1)}),\varphi(p^{\nu_p(d_2)}))} = \frac{\varphi(q)}{\prod_{p|q} \mathrm{lcm}(\varphi(p^{\nu_p(d_1)}),\varphi(p^{\nu_p(d_2)}))}.$$ Notice that this product does not collapse into$\frac{\varphi(q)}{\mathrm{lcm}(\varphi(d_1),\varphi(d_2))}$.</p> http://mathoverflow.net/questions/30204/integer-values-of-a-rational-function Integer values of a rational function Max Alekseyev 2010-07-01T16:15:17Z 2012-11-26T20:22:00Z <p>Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the function takes integer values?</p> <p>In other words, for given polynomials$F(x)$and$G(x)$with integer coefficients, how to compute efficiently all such integers$m$that$G(m)$divides$F(m)$?</p> <p>I've developed a rather straight forward approach to this problem at <a href="http://list.seqfan.eu/pipermail/seqfan/2010-April/004339.html" rel="nofollow">http://list.seqfan.eu/pipermail/seqfan/2010-April/004339.html</a> but I suspect it is far from optimal.</p> http://mathoverflow.net/questions/113964/solving-equations-in-a-subset-of-rational-numbers Solving equations in a subset of rational numbers Max Alekseyev 2012-11-20T17:04:43Z 2012-11-21T02:07:51Z <p>Let$S$be a set of all positive rational numbers$x$such that$2x^2 - 1$is a square, excluding$x=1$.</p> <p>I am interested in computing as many as possible solutions in$S$to either the following equations:</p> <p>(1)$\qquad p^2 - 1 = (q^2 - 1)\cdot r^2$</p> <p>(2) ...removed...</p> <p>(3)$\qquad p^2 + q^2 = 1 + r^2$</p> <p>What would a reasonable computational approach for finding solutions?</p> <p>For the equation (1), I know one solution:$(p,q,r)=(\tfrac{373}{23}, \tfrac{85}{41}, \tfrac{205}{23})$-- would it help to find more solutions? </p> <p>EDIT: Equation (2) was not exactly the one I'm interested in. So I removed it.</p> http://mathoverflow.net/questions/96334/efficient-counting-of-egyptian-fractions-with-bounded-denominators Efficient counting of Egyptian fractions with bounded denominators Max Alekseyev 2012-05-08T12:52:54Z 2012-05-08T12:58:48Z <p>I was amazed to discover that sequence <a href="http://oeis.org/A020473" rel="nofollow">http://oeis.org/A020473</a> in the OEIS has almost four hundred terms computed. </p> <p>I wonder how one can get that far? E.g., how one can compute A020473(100)?</p> <p>P.S. There was a related question <a href="http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1" rel="nofollow">http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1</a> about Egyptian fractions with a fixed number of reciprocals (with unbounded denominators) for which there seemed to be no efficient counting algorithm (to compute hundreds of terms) known. I found it interesting how complexity of these two problems differ.</p> http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex/96228#96228 Answer by Max Alekseyev for A simple looking problem in partitions that became increasingly complex Max Alekseyev 2012-05-07T15:22:46Z 2012-05-07T15:22:46Z <p>I've got the following counts (which agrees with Brendan's):</p> <p>1: 1</p> <p>2: 3</p> <p>3: 10</p> <p>4: 55</p> <p>5: 196</p> <p>6: 2730</p> <p>7: 10032</p> <p>8: 108999</p> <p>9: 973258</p> <p>10: 20780331</p> <p>11: 79309308</p> <p>12: 2614200602</p> <p>13: 10073335754</p> <p>14: 288845706742</p> <p>15: 11805287917646</p> <p>16: 254331289285523</p> http://mathoverflow.net/questions/80194/difference-equation-an-xpxan-1-x-1qxan-1-x/80206#80206 Answer by Max Alekseyev for Difference equation$A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$Max Alekseyev 2011-11-06T11:01:50Z 2011-11-06T11:38:26Z <p>Let $$P_m(x,z) = \prod_{k=0}^{m-1} (p(x-k)+q(x-k)z)$$ and $$\mathcal{A_n}(x,z) = \sum_{k=0}^{\infty} A(n,x-k) z^k.$$</p> <p>Then unrolling the given recurrence$m$times, we get that$A(n,x)$equals the coefficient of$z^m$in $$P_m(x,z)\cdot \mathcal{A}_{n-m}(x,z).$$ In particular, for$A(n,x)$equals the coefficient of$z^n$in $$P_n(x,z)\cdot \mathcal{A}_{0}(x,z).$$</p> <p>More could be said if the boundary constraints were given.</p> http://mathoverflow.net/questions/78987/deriving-a-closed-form-for-rolling-a-sum-n-with-k-dice-using-stars-and-bars/79058#79058 Answer by Max Alekseyev for Deriving a closed form for rolling a sum$n$with$k$dice using stars and bars Max Alekseyev 2011-10-25T08:51:17Z 2011-10-25T09:02:40Z <p>Answer is given by the coefficient of$z^n$in $$(z+z^2+\dots+z^6)^k = \left(z\frac{1-z^6}{1-z}\right)^k = z^k (1-z^6)^k(1-z)^{-k}.$$ An explicit formula for this coefficient is: $$\sum_{i=0}^{\min(k,\lfloor (n-k)/6\rfloor)} (-1)^{n+i} \binom{k}{i} \binom{-k}{n-k-6i} = \sum_{i=0}^{\min(k,\lfloor (n-k)/6\rfloor)} (-1)^i \binom{k}{i} \binom{n-6i-1}{k-1}.$$</p> http://mathoverflow.net/questions/78650/polynomial-of-degree-n-with-integer-coefficient-for-a-given-root/78688#78688 Answer by Max Alekseyev for Polynomial of degree N with integer coefficient for a given root. Max Alekseyev 2011-10-20T18:08:02Z 2011-10-20T18:16:49Z <p>The problem can be solved by running some Integer Relation algorithm (e.g., PSLQ) on the numbers$1, r, r^2, \dots, r^N$where$r$is a given root.</p> <p>See <a href="http://en.wikipedia.org/wiki/Integer_relation_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Integer_relation_algorithm</a></p> <p>For example, here is computation in PARI/GP which gives a better result than the polynomial shown in question: </p> <p>? r = 28.552622898861801; algdep(r,10)</p> <p>%1 = 3*x^10 + 38*x^9 - 3695*x^8 + 4582*x^7 + 3016*x^6 + 1435*x^5 + 4552*x^4 - 1219*x^3 - 9920*x^2 - 2402*x + 3087</p> <p>? subst(%1,x,r)</p> <p>%2 = -2.7334689816478450022 E-24</p> http://mathoverflow.net/questions/74664/some-weird-system-of-inequalities-in-nonnegative-integers/74691#74691 Answer by Max Alekseyev for Some weird "system" of inequalities in nonnegative integers. Max Alekseyev 2011-09-06T22:45:45Z 2011-09-24T21:40:11Z <p>Take$a_{iiii}=0$for all$i=1,\dots,17$and let the other$a$'s be arbitrary large. Then the inequality is satisfied.</p> <p>Indeed, let$w_1, \dots, w_{17}$be arbitrary nonnegative integers. Without loss of generality assume that $$\min \{ w_1, \dots, w_{17} \} = w_1.$$ Then $$\min_{1\leq i\leq j\leq k\leq l\leq 17} (a_{ijkl} + w_i + w_j + w_k + w_l) \leq a_{1111} + 4w_1 = 4w_1 \leq \frac{4}{17} \sum_{t=1}^{17} w_t$$ as required.</p> <p>Hence,$a_{ijkl}$are not bounded in general.</p> http://mathoverflow.net/questions/76235/hitting-set-problem-variant/76281#76281 Answer by Max Alekseyev for Hitting set problem variant Max Alekseyev 2011-09-24T18:59:55Z 2011-09-24T19:05:52Z <p>Let$\mathcal{E} = \bigcup_{k=1}^m E_k.$</p> <p>For each$j\in\mathcal{E}$, let$A_j = \{ k\in [1,m] : j\in E_k \}$. Then the anticipated subset$I\subset\mathcal{E}$should satisfy the following requirements: $$\bigcup_{i\in I} A_i = \{ 1, 2, \dots, m \}$$ and $$\forall i\in I\quad A_i\not\subset \bigcup_{j\in I\atop j\ne i} A_j.$$ (the latter means that there exists$k\in A_i$such that$k\not\in A_j$for all$j\in I\setminus\{i\}$, that is,$E_k\cap I=\{i\}$)</p> <p>That is, the collection$\{ A_i : i\in I\}$forms a minimal cover of the set$\{ 1, 2, \dots, m\}$. Such cover always exists -- one can start with the collection$\{ A_j : j\in\mathcal{E} \}$and iteratively remove$A_i$that is a subset of the union of the remaining sets until no such sets left.</p> <p>In the example with$E_1=\{1,2\}$,$E_2=\{2,3\}$and$E_3=\{1,3\}$we have$A_1 = \{1,3\}$,$A_2 = \{ 1,2\}$,$A_3=\{2,3\}$. Clearly, removing any set from the collection$\{ A_1, A_2, A_3 \}$leaves us with a solution.</p> http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates/75498#75498 Answer by Max Alekseyev for Computing Permutations with Partial Duplicates Max Alekseyev 2011-09-15T09:12:48Z 2011-09-17T07:51:54Z <p>The number of$K$-permutations of the numtiset${ 1^D, 2^D, \ldots, N^D }$is $$\sum_{j_1+j+2+\dots+j_N=K\atop 0 \leq j_i \leq D} \binom{K}{j_1,j_2,\dots,j_N}.$$ (summands here are multinomial coefficients)</p> <p>Alternatively, denoting by$m_i$the number of$j$'s equal$i$, we get a formula as the sum over restricted partitions: $$\sum_{0m_0+1m_1 + \dots + Dm_D = K\atop m_0 + m_1 + \dots + m_D = N,\quad m_i\geq 0} \binom{N}{m_0,\dots,m_D} \frac{K!}{1!^{m_1} 2!^{m_2} \cdots D!^{m_D}}$$</p> <p>For the example with$N=9$,$D=3$,$K=4$, the latter formula consists of four summands and gives: $$\binom{9}{5,4} \frac{4!}{1!^4} + \binom{9}{6,2,1}\frac{4!}{1!^2 2!^1} + \binom{9}{7,1,1}\frac{4!}{1!^1 3!^1} + \binom{9}{7,2}\frac{4!}{2!^2}$$ $$= 3024 + 3024 + 288 + 216 = 6552$$ as expected.</p> http://mathoverflow.net/questions/70406/bilinear-system-of-diophantine-equations/73839#73839 Answer by Max Alekseyev for Bilinear system of Diophantine Equations Max Alekseyev 2011-08-27T11:57:44Z 2011-08-27T11:57:44Z <p>Let's first focus on the equations: $$\sum_{j=1, j\ne i}^n x_j y_j = -n_{ii} + x_i y_i.$$ Denoting$s = \sum_{j=1}^n x_j y_j$, we have $$2x_iy_i = n_{ii} + s.$$ Summing up over$i=1,2,\dots,n$, we get $$2s = \sum_{i=1}^n n_{ii} + n\cdot s.$$ implying that (for$n\ne 2$) $$s = \frac{-1}{n-2} \sum_{i=1}^n n_{ii},$$ Therefore, $$x_i y_i = n_{ii} - \frac{1}{n-2} \sum_{i=1}^n n_{ii}.$$</p> <p>Now, the equation $$x_i y_j + x_j y_i = n_{ij}$$ multiplied by$2 x_i x_j$turns into $$(n_{jj} + s) x_i^2 + (n_{ii} + s) x_j^2 = 2 n_{ij} x_i x_j.$$ Plugging in$j=1$and dividing by$x_1^2$, we further have $$(n_{11} + s) z_i^2 - 2 n_{i1} z_i + (n_{ii} + s) = 0$$ which is a quadratic equation w.r.t.$z_i = x_i / x_1$and can be easily solved.</p> <p>Values of$y_i$can be found similarly.</p> http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients/73639#73639 Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients? Max Alekseyev 2011-08-25T08:12:12Z 2011-08-25T08:12:12Z <p>Another way to approach the original problem is to recall the formula: $$\cos(y)^k = \frac{1}{2^k} \sum_{j=0}^k \binom{k}{j}\cos((k-2j)y).$$ Plugging in$y=\frac{\pi}{2} - x$would give an expansion for$\sin(x)^k$. I suspect eventually it would lead to the same formula that I gave in the previous answer.</p> http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients/73616#73616 Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients? Max Alekseyev 2011-08-24T22:38:05Z 2011-08-24T22:49:45Z <p>$\binom{\ell}{a_1,\dots,a_k}$is the coefficient of$x_1^{a_1}\cdots x_k^{a_k}$in the expansion of $$(x_1 + x_2 + \dots + x_k)^{\ell}.$$ The sum of all these coefficients is obtained by substituting$x_1=\dots=x_k=1$.</p> <p>To eliminate even$a_1$, we can consider the expansion of $$\frac{1}{2}(x_1 + x_2 + \dots + x_k)^{\ell} - \frac{1}{2}(-x_1 + x_2 + \dots + x_k)^{\ell}.$$</p> <p>Continuing this way, we eventually get $$s(\ell,k) = \frac{1}{2^k} \sum_{t_1,\dots,t_k=0}^1 (-1)^{t_1+\dots+t_k} ((-1)^{t_1}+\cdots+(-1)^{t_k})^{\ell}$$ $$=\frac{1}{2^k} \sum_{z=0}^k \binom{k}{z} (-1)^z (k-2z)^{\ell}.$$</p> <p>P.S. This formula resembles one for Stirling number of the second kind (formula (10) at <a href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html" rel="nofollow">MathWorld</a>) but not quite.</p> http://mathoverflow.net/questions/70543/edge-covering-shortest-path/70566#70566 Answer by Max Alekseyev for Edge Covering Shortest path Max Alekseyev 2011-07-17T20:14:57Z 2011-07-17T20:27:27Z <p>That is Chinese Postman Path. Search for Chinese Postman Problem...</p> <p>E.g., this section from some book looks comprehensive: <a href="http://academic.cankaya.edu.tr/~kandiller/eski_ie454/Chp-03%20044-064.pdf" rel="nofollow">http://academic.cankaya.edu.tr/~kandiller/eski_ie454/Chp-03%20044-064.pdf</a></p> http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem/64987#64987 Answer by Max Alekseyev for "Bipartite" Travelling Salesman Problem? Max Alekseyev 2011-05-14T14:27:26Z 2011-05-14T14:27:26Z <p>Looks like you are looking for maximum weighted bipartite matching - if so, see <a href="http://en.wikipedia.org/wiki/Maximal_matching#Maximum_matchings_in_bipartite_graphs" rel="nofollow">Wikipedia</a> for initial pointers.</p> http://mathoverflow.net/questions/62619/generalized-vieta-product/63235#63235 Answer by Max Alekseyev for Generalized Vieta-product Max Alekseyev 2011-04-27T21:47:11Z 2011-04-28T18:33:17Z <p>I doubt there exists a closed formula for$n\ne 2$. In the case$n=2$such formula exists only thanks to the double-angle formula for cosine.</p> <p>Let$n$be fixed and$c=c_n$. Notice that$n=c^2-c$and$c\to\infty$as soon as$n\to\infty$.</p> <p>Denote by$p_k$the$k$-th multiplier in the product$S_n$. It can be easily seen that $$c\cdot (p_k^2-1) = p_{k-1} - 1$$</p> <p>Consider the functional equation: $$c\cdot(f(x)^2-1)=f(2cx)-1$$ with$f(0)=1$and$f'(0)=1$. Its solution can be expressed as a series: $$f(x) = 1 + x + \frac{x^2}{2(2c-1)} + \frac{x^3}{2(2c-1)^2(2c+1)} + \frac{x^4(2c+5)}{8(2c-1)^3(2c+1)(4c^2+2c+1)} + \dots.$$ Then $$p_k = f\left(\frac{x_0}{(2c)^k}\right)$$ where$x_0$is a solution to$f(x_0)=0$.</p> <p>Now $$S_n = \prod_{k=1}^{\infty} p_k = \exp \sum_{k=1}^{\infty} \ln\left(1 + \Theta\left(\frac{x_0}{(2c)^k}\right) \right) = \exp \sum_{k=1}^{\infty} \Theta\left(\frac{x_0}{(2c)^k}\right) = \exp \Theta\left(\frac{x_0}{2c-1}\right)$$ which tends to$1$as$c\to\infty$.</p> <p>Therefore,$S_n\to 1$as$n\to\infty$.</p> <p><strong>Example</strong>. For$n=2$, the functional equation admits the analytic solution$f(x)=\cosh(\sqrt{2x})$for which$x_0=\frac{-\pi^2}{8}$.</p> http://mathoverflow.net/questions/28649/how-many-hamiltonians-paths-there-are-in-almost-regular-graph/29857#29857 Answer by Max Alekseyev for How many Hamiltonians Paths there are in almost regular graph ? Max Alekseyev 2010-06-29T01:54:56Z 2011-04-20T21:19:01Z <p>Explicit values for$k\leq 9$and small$n$are given in the OEIS:</p> <p>k=2: <a href="http://oeis.org/A003274" rel="nofollow">http://oeis.org/A003274</a> (contains some references and a generating function)</p> <p>k=3: <a href="http://oeis.org/A174700" rel="nofollow">http://oeis.org/A174700</a></p> <p>k=4: <a href="http://oeis.org/A174701" rel="nofollow">http://oeis.org/A174701</a></p> <p>k=5: <a href="http://oeis.org/A174702" rel="nofollow">http://oeis.org/A174702</a></p> <p>k=6: <a href="http://oeis.org/A177278" rel="nofollow">http://oeis.org/A177278</a></p> <p>k=7: <a href="http://oeis.org/A177279" rel="nofollow">http://oeis.org/A177279</a></p> <p>k=8: <a href="http://oeis.org/A177280" rel="nofollow">http://oeis.org/A177280</a></p> <p>k=9: <a href="http://oeis.org/A177281" rel="nofollow">http://oeis.org/A177281</a></p> http://mathoverflow.net/questions/62302/examples-of-amenable-groups-other-than-z-n/62341#62341 Answer by Max Alekseyev for Examples of Amenable Groups other than Z_n Max Alekseyev 2011-04-19T21:33:55Z 2011-04-19T21:33:55Z <p>$\mathrm{Symm}(\mathbb{Z}) \leftthreetimes \mathbb{Z}$- see page 4321 in <a href="http://www.cse.sc.edu/~maxal/a-g-g.pdf" rel="nofollow">http://www.cse.sc.edu/~maxal/a-g-g.pdf</a></p> http://mathoverflow.net/questions/123459/when-adding-a-constant-makes-a-multivariate-polynomial-reducible Comment by Max Alekseyev Max Alekseyev 2013-03-03T08:32:01Z 2013-03-03T08:32:01Z @Aakumadula: Thanks for answering the third question! http://mathoverflow.net/questions/120963/a-formula-combining-euler-phi-and-gcd/123408#123408 Comment by Max Alekseyev Max Alekseyev 2013-03-02T12:44:15Z 2013-03-02T12:44:15Z Last sentence: &quot;That is, there exist integers$a_1,\dots,a_n$with$0\leq a_i&lt;N$that satisfy congruences$(\star)$and thus$\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$.&quot; http://mathoverflow.net/questions/123122/when-polynomial-fx2-can-be-factored-as-gxg-x Comment by Max Alekseyev Max Alekseyev 2013-02-28T14:00:06Z 2013-02-28T14:00:06Z @Lierre: I'm just asking if there exists anything more efficient in this special case. http://mathoverflow.net/questions/123122/when-polynomial-fx2-can-be-factored-as-gxg-x/123139#123139 Comment by Max Alekseyev Max Alekseyev 2013-02-27T20:56:56Z 2013-02-27T20:56:56Z I'm confused by$p$being a modulus and an irreducible factor at the same time. http://mathoverflow.net/questions/123122/when-polynomial-fx2-can-be-factored-as-gxg-x/123134#123134 Comment by Max Alekseyev Max Alekseyev 2013-02-27T20:36:29Z 2013-02-27T20:36:29Z So what you are proposing is not better than just factoring$f(x^2)$, is it? http://mathoverflow.net/questions/123058/expression-for-the-sum-of-square-roots-of-zeros-of-a-polynomial/123091#123091 Comment by Max Alekseyev Max Alekseyev 2013-02-27T15:49:12Z 2013-02-27T15:49:12Z In general case, I agree. But I have a hope that something better can be done in the special case when$f(y^2) = g(y)\cdot g(-y)$. http://mathoverflow.net/questions/121488/a-sum-involving-modn-arithmetic Comment by Max Alekseyev Max Alekseyev 2013-02-11T17:53:43Z 2013-02-11T17:53:43Z There are no 1s in your question. And what is$k$in the right hand side of the second formula? http://mathoverflow.net/questions/120674/what-is-the-cardinality-of-the-family-of-unlabelled-bipartite-graphs-on-n-vertice Comment by Max Alekseyev Max Alekseyev 2013-02-04T02:55:15Z 2013-02-04T02:55:15Z It look to me that the given counting for labeled bipartite graphs is incorrect. Labeling of vertices does not imply particular partition of the vertices into V_1 and V_2. E.g., an isolated vertex may be viewed as belonging to V_1 or V_2 but that does not change the graph. http://mathoverflow.net/questions/116137/the-bch-series-in-terms-of-lyndon-words Comment by Max Alekseyev Max Alekseyev 2012-12-16T19:11:32Z 2012-12-16T19:11:32Z I tool a liberty to add this sequence to the OEIS as <a href="http://oeis.org/A220587" rel="nofollow">oeis.org/A220587</a> http://mathoverflow.net/questions/115039/generalization-of-lagrange-inversion-with-skewed-formal-parameter Comment by Max Alekseyev Max Alekseyev 2012-12-01T06:57:37Z 2012-12-01T06:57:37Z Just to double check: there is no$t$in your implicit equation - is it correct? http://mathoverflow.net/questions/114824/how-to-solve-a-specific-multivariate-recurrence-relation-or-general-ones Comment by Max Alekseyev Max Alekseyev 2012-11-29T05:17:26Z 2012-11-29T05:17:26Z What is$f(0,b)$for$b&gt;0$? http://mathoverflow.net/questions/114824/how-to-solve-a-specific-multivariate-recurrence-relation-or-general-ones Comment by Max Alekseyev Max Alekseyev 2012-11-29T05:05:02Z 2012-11-29T05:05:02Z The constraint$a \leq \min(n,b)$can be replaced by simply$a \leq b$(values$f(a,b)$for$a&gt;n$can be set to zero later). The reason is that if the first argument of$f(,)$in the l.h.s. of the recurrent formula is$\leq n$, then so are the first arguments of$f(,)$in the r.h.s. http://mathoverflow.net/questions/113964/solving-equations-in-a-subset-of-rational-numbers/113978#113978 Comment by Max Alekseyev Max Alekseyev 2012-11-20T23:03:20Z 2012-11-20T23:03:20Z Thanks! I've tried this approach but I also have no idea what to do with the resulting high-degree Diophantine equations. I would probably give up if I had just an equation like the one you derived. But I hope that the original formulation may provide additional insights into the structure of solutions and somehow simplify their search. http://mathoverflow.net/questions/88929/a-family-of-pellian-equations Comment by Max Alekseyev Max Alekseyev 2012-11-13T23:41:51Z 2012-11-13T23:41:51Z Just a simple observation: this equation is equivalent to$x^2+1=(y^2+1)(k^2+1)$, i.e., when the product of two numbers of the form$m^2+1\$ is again a number of this form. http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex Comment by Max Alekseyev Max Alekseyev 2012-05-08T12:56:39Z 2012-05-08T12:56:39Z I asked a question about computing terms of related sequence <a href="http://oeis.org/A020473" rel="nofollow">oeis.org/A020473</a> at <a href="http://mathoverflow.net/questions/96334/efficient-counting-of-egyptian-fractions-with-bounded-denominators" rel="nofollow" title="efficient counting of egyptian fractions with bounded denominators">mathoverflow.net/questions/96334/&hellip;</a> It may happen that the same approach can be used for efficient counting number of solutions to the discussed equation.