User max alekseyev - MathOverflow

Answer by Max Alekseyev for Transforming a Diophantine equation to an elliptic curve

2010-06-29T23:29:23Z

Allan MacLeod's website Elliptic Curves in Recreational Number Theory considers this problem among many other interesting ones.

Transformation of a bivariate polynomial into a homogeneous one

2013-02-27T02:35:34Z

For a given a bivariate polynomial $P(x,y)$ with rational coefficients:

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

Q2. Can the degree of $H$ be minimized? Can maximum degree of $H,S,T$ be minimized?

Example. 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.S. Trivial representation with $H(u,v)=u$ and $u=P(x,y)$, $v=0$ is unacceptable as non-invertible.

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.

Expression for the sum of square roots of zeros of a polynomial

2013-02-27T01:56:52Z

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

General question. 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)$ ?

Remark. 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 nonnegative integer $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$:

$n=1:\qquad r^2 - s_1 = 0$

$n=2:\qquad r^4 - 2 s_1 r^2 + (2 s_2 - s_1^2) = 0$

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

$n=4:\qquad 9 r^{16} - 72 s_1 r^{14} + (180 s_1^2 + 72 s_2) r^{12} + \dots = 0$

Unfortunately the degree of these polynomials grows as $2^n$, and in general it seems it cannot be made much smaller.

Specific question. 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?

Answer by Max Alekseyev for Like Diophantine equation

2013-03-03T08:28:07Z

The equation $x^n - ny^x - nxy = 0$ has no solutions in positive integers.

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.

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

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 < xv+w$ unless $v=0$. So there are two cases to consider:

1) $v=0$. In this case we have $xv+w = w < u+v+w$ and $xv+w = w < p^w \leq nu$, that is $\nu_p(ny^x)$ is a sole smallest valuation among the three, which is impossible.

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.

When adding a constant makes a multivariate polynomial reducible?

2013-03-03T05:23:46Z

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?

Are there any simple criteria to identify cases when such $m$ does not exist?

Is it possible that more than one suitable values of $m$ exist?

Answer by Max Alekseyev for A formula combining Euler $\phi$ and $\gcd$

2013-03-02T12:41:07Z

Below I characterize set of values achievable by $\psi(a_1,\dots,a_n;N)$.

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

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

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

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

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

When polynomial f(x^2) can be factored as g(x)·g(-x) ?

2013-02-27T17:45:46Z

In relation to my question http://mathoverflow.net/questions/123058/expression-for-the-sum-of-square-roots-of-zeros-of-a-polynomial

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?

Is there a computationally efficient way to identify if given polynomial $f(x)$ is such without factoring $f(x^2)$ ?

Answer by Max Alekseyev for Hexagonal Triangular Squares

2010-07-14T23:07:13Z

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: http://arxiv.org/abs/1002.1679 (see Theorem 6)

It is easy to obtain that the only nonegative solution is $n=1$, $m=1$, $p=0$.

Answer by Max Alekseyev for Almost-converses to the AM-GM inequality

2013-02-20T19:40:41Z

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.

See http://en.wikipedia.org/wiki/Generalized_mean#Generalized_mean_inequality

Answer by Max Alekseyev for Formula for finite sum

2013-02-20T19:28:20Z

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

Answer by Max Alekseyev for NP Complete for range sum constraints?

2010-06-29T23:15:53Z

The problem is equivalent to checking whether the vector $(h_1,\dots,h_m)$ belong to the integer lattice $$\{ 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$.

However, there exists a similar problem that is indeed $NP$-complete - namely, checking whether a given vector belongs to the integer cone $$\{ Ax \mid x\in \mathbb{Z}_+^n \}.$$

The crucial difference is that in the first problem variables $x_1,\dots,x_n$ can be arbitrary integers, while in the second problem they have to be nonnegative integers. And this nonnegativity requirement turns a polynomial-time problem into an $NP$-complete one.

Answer by Max Alekseyev for A sum involving mod(n) arithmetic

2013-02-12T13:48:26Z

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.

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

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},& \text{if}\ s_1=s_2=0\\ p^{t-\max\{s_1,s_2\}},&\text{otherwise}. \end{cases}$$

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

Integer values of a rational function

2010-07-01T16:15:17Z

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?

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

I've developed a rather straight forward approach to this problem at http://list.seqfan.eu/pipermail/seqfan/2010-April/004339.html but I suspect it is far from optimal.

Solving equations in a subset of rational numbers

2012-11-20T17:04:43Z

Let $S$ be a set of all positive rational numbers $x$ such that $2x^2 - 1$ is a square, excluding $x=1$.

I am interested in computing as many as possible solutions in $S$ to either the following equations:

(1) $\qquad p^2 - 1 = (q^2 - 1)\cdot r^2$

(2) ...removed...

(3) $\qquad p^2 + q^2 = 1 + r^2$

What would a reasonable computational approach for finding solutions?

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?

EDIT: Equation (2) was not exactly the one I'm interested in. So I removed it.

Efficient counting of Egyptian fractions with bounded denominators

2012-05-08T12:52:54Z

I was amazed to discover that sequence http://oeis.org/A020473 in the OEIS has almost four hundred terms computed.

I wonder how one can get that far? E.g., how one can compute A020473(100)?

P.S. There was a related question http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1 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.

Answer by Max Alekseyev for A simple looking problem in partitions that became increasingly complex

2012-05-07T15:22:46Z

I've got the following counts (which agrees with Brendan's):

1: 1

2: 3

3: 10

4: 55

5: 196

6: 2730

7: 10032

8: 108999

9: 973258

10: 20780331

11: 79309308

12: 2614200602

13: 10073335754

14: 288845706742

15: 11805287917646

16: 254331289285523

Answer by Max Alekseyev for Difference equation $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

2011-11-06T11:01:50Z

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

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

More could be said if the boundary constraints were given.

Answer by Max Alekseyev for Deriving a closed form for rolling a sum $n$ with $k$ dice using stars and bars

2011-10-25T08:51:17Z

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

Answer by Max Alekseyev for Polynomial of degree N with integer coefficient for a given root.

2011-10-20T18:08:02Z

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.

See http://en.wikipedia.org/wiki/Integer_relation_algorithm

For example, here is computation in PARI/GP which gives a better result than the polynomial shown in question:

? r = 28.552622898861801; algdep(r,10)

%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

? subst(%1,x,r)

%2 = -2.7334689816478450022 E-24

Answer by Max Alekseyev for Some weird "system" of inequalities in nonnegative integers.

2011-09-06T22:45:45Z

Take $a_{iiii}=0$ for all $i=1,\dots,17$ and let the other $a$'s be arbitrary large. Then the inequality is satisfied.

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.

Hence, $a_{ijkl}$ are not bounded in general.

Answer by Max Alekseyev for Hitting set problem variant

2011-09-24T18:59:55Z

Let $\mathcal{E} = \bigcup_{k=1}^m E_k.$

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\}$)

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.

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.

Answer by Max Alekseyev for Computing Permutations with Partial Duplicates

2011-09-15T09:12:48Z

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)

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

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.

Answer by Max Alekseyev for Bilinear system of Diophantine Equations

2011-08-27T11:57:44Z

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

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.

Values of $y_i$ can be found similarly.

Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients?

2011-08-25T08:12:12Z

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.

Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients?

2011-08-24T22:38:05Z

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

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

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.S. This formula resembles one for Stirling number of the second kind (formula (10) at MathWorld) but not quite.

Answer by Max Alekseyev for Edge Covering Shortest path

2011-07-17T20:14:57Z

That is Chinese Postman Path. Search for Chinese Postman Problem...

E.g., this section from some book looks comprehensive: http://academic.cankaya.edu.tr/~kandiller/eski_ie454/Chp-03%20044-064.pdf

Answer by Max Alekseyev for "Bipartite" Travelling Salesman Problem?

2011-05-14T14:27:26Z

Looks like you are looking for maximum weighted bipartite matching - if so, see Wikipedia for initial pointers.

Answer by Max Alekseyev for Generalized Vieta-product

2011-04-27T21:47:11Z

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.

Let $n$ be fixed and $c=c_n$. Notice that $n=c^2-c$ and $c\to\infty$ as soon as $n\to\infty$.

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

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

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

Therefore, $S_n\to 1$ as $n\to\infty$.

Example. For $n=2$, the functional equation admits the analytic solution $f(x)=\cosh(\sqrt{2x})$ for which $x_0=\frac{-\pi^2}{8}$.

Answer by Max Alekseyev for How many Hamiltonians Paths there are in almost regular graph ?

2010-06-29T01:54:56Z

Explicit values for $k\leq 9$ and small $n$ are given in the OEIS:

k=2: http://oeis.org/A003274 (contains some references and a generating function)

k=3: http://oeis.org/A174700

k=4: http://oeis.org/A174701

k=5: http://oeis.org/A174702

k=6: http://oeis.org/A177278

k=7: http://oeis.org/A177279

k=8: http://oeis.org/A177280

k=9: http://oeis.org/A177281

Answer by Max Alekseyev for Examples of Amenable Groups other than Z_n

2011-04-19T21:33:55Z

$\mathrm{Symm}(\mathbb{Z}) \leftthreetimes \mathbb{Z}$ - see page 4321 in http://www.cse.sc.edu/~maxal/a-g-g.pdf

Comment by Max Alekseyev

2013-03-03T08:32:01Z

@Aakumadula: Thanks for answering the third question!

Comment by Max Alekseyev

2013-03-02T12:44:15Z

Last sentence: "That is, there exist integers $a_1,\dots,a_n$ with $0\leq a_i<N$ that satisfy congruences $(\star)$ and thus $\gcd(a_1,\dots,a_i+1,\dots,a_n,N)=d_i$."

Comment by Max Alekseyev

2013-02-28T14:00:06Z

@Lierre: I'm just asking if there exists anything more efficient in this special case.

Comment by Max Alekseyev

2013-02-27T20:56:56Z

I'm confused by $p$ being a modulus and an irreducible factor at the same time.

Comment by Max Alekseyev

2013-02-27T20:36:29Z

So what you are proposing is not better than just factoring $f(x^2)$, is it?

Comment by Max Alekseyev

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

Comment by Max Alekseyev

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?

Comment by Max Alekseyev

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.

Comment by Max Alekseyev

2012-12-16T19:11:32Z

I tool a liberty to add this sequence to the OEIS as oeis.org/A220587

Comment by Max Alekseyev

2012-12-01T06:57:37Z

Just to double check: there is no $t$ in your implicit equation - is it correct?

Comment by Max Alekseyev

2012-11-29T05:17:26Z

What is $f(0,b)$ for $b>0$ ?

Comment by Max Alekseyev

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

Comment by Max Alekseyev

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.

Comment by Max Alekseyev

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.

Comment by Max Alekseyev

2012-05-08T12:56:39Z

I asked a question about computing terms of related sequence oeis.org/A020473 at mathoverflow.net/questions/96334/… It may happen that the same approach can be used for efficient counting number of solutions to the discussed equation.