User falagar - MathOverflow

Problems known to be in both NP and coNP, but not known to be in P

2010-07-14T10:03:22Z

One such problem I know is integer factorization.

What are other interesting cases?

Inverting the totient function

2010-07-13T12:12:57Z

For what values of $n$ does the equation $\phi(x) = n$ have at least one solution? Is there any efficient way to check it for a given $n$?

It obviously has no solutions for odd $n$. And the smallest even number for which it has no solutions is $14$.

Function with range equal to whole reals on every open set

2010-07-16T07:05:46Z

There is an example of a function that is unbounded on every open set. Just take $f(n/m) = m$ for coprime $n$ and $m$ and $f(irrational) = 0$.

I want to generalize this in a way to get a function which is not just unbounded on every open set, but whose range is equal to $\mathbb{R}$ on every open set. The latter construction clearly doesn't work.

I'm interested whether such function exists and if it exists is there any constructive way to define it?

Answer by falagar for dynamic programming and combinatorics

2010-08-13T11:26:42Z

You can use dynamic programming as you suggest in the title.

Let $w_{ij}$ be the max gain you can get putting $j$ balls into first $i$ buckets.

Then $w_{ij}$ has the following recursive relation: $$ w_{i,j} = \max_{0 \le t \le \min(N-1, j)}(w_{i-1,j-t} + \Delta l_{i, t}) $$

There $t$ is the number of balls you put into $i$-th bucket. Hence you can calculate $w_{K, \lambda}$ (your answer) in time $O(K \lambda N)$.

Answer by falagar for Finding all cycles of a certain length in a graph

2010-08-13T09:14:18Z

If you consider only simple cycles (every vertex visited at most once) then this problem is NP-complete, so no polynomial (in $|G|$ and $k$) algorithm is known.

If non-polynomial algorithms are ok, you can use dynamic programming algorithm with complexity $O(\sum_{i=0}^{i\le k}\binom{n}{i}n^2)$. This algorithm calculates for every subset $S$ of at most $k$ vertices and every vertex $v \in S$ from this subset the number of paths that goes through all vertices from $S$ and has $v$ as the last vertex.

Polynomial with prime powers values

2010-08-12T11:17:06Z

It's well known that there are no non-constant polynomials with integer coefficients whose values at integer points are primes. Could this result be generalized to the case of prime powers?

The question is whether there exists a polynomial $p(x) \in \mathbb{Z}[x]$ with degree at least one such that for all $x \in \mathbb{Z}$ $|p(x)|$ is prime power.

Answer by falagar for Consecutive integers with many prime factors

2010-08-12T15:18:30Z

Answer for the first question. Let $w_k$ be the product $p_{nk+1} p_{nk+2} \cdots p_{nk+n}$ where $p_i$ is $i$-th prime. So each $w_k$ is equal to product of $n$ distinct primes and $w_k$ and $w_q$ are coprime for $k \ne q$. Now take $t$ such that $t \equiv -k \pmod {w_k}$ for $k = 1, 2, \cdots, m$. Such $t$ exists by Chinese Remainder Theorem. Now $t + k$ has at least $n$ primes because $t + k$ is a multiple of $w_k$. Hence numbers $t + 1, t + 2, \cdots, t + m$ satisfy requirements in the first question.

Answer by falagar for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:09:05Z

If $n_1$ and $n_2$ are not too big you can use Eratosthenes sieve (see wikipedia for this). If they are big enought you can use sieve to cross out numbers which have small prime divisors and after that check every number that wasn't crossed out and check if it is prime using any primality test (see http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test).

Special cases of Dirichlet's theorem

2010-07-20T12:14:10Z

Dirichlet's theorem states that for any coprime $k$ and $m$ there exists infinitely many primes $p$ such that $p \equiv k \pmod m$.

Some special cases of this theorem are easy to prove without any analytic methods. Those cases include, for example, $m=4, k=1$ and $m=4, k=3$.

Both cases could be proved by considering first $t$ prime numbers $p_i \equiv k \pmod m$ and constructing a new number which is proved to have prime divisor $p \equiv k \pmod m$ that is not equal to any $p_i$.

For case $m=4, k=1$ we can consider number $(p_1 p_2 \cdots p_t)^2 + 1$. And for case $m=4, k=3$ number $4p_1 p_2 \cdots p_k + 3$.

Those constructions could also be applied to some other special cases as well.

Are there any other special cases for which there exists a simple non-analytic proof which don't use any of those two constructions?

Answer by falagar for Does there exist a pure recurrence formula with polynomial coefficients for Fibonacci(2^n)?

2010-07-21T10:10:02Z

There is the following formula: $$ x_{n+2} = \frac{x_{n+1}^3}{2 x_{n}^2} + \frac{5}{2} x_n^2 x_{n+1} $$ I'm not sure if this is a pure recurrence formulae. If you need, I may provide a proof.

Representation of rational numbers as the sum of 1/k

2010-07-22T13:54:47Z

Is it true that every positive rational number $r = \frac{n}{m}$ could be represented as sum of $\frac{1}{k}$ for different $k$'s:

$$ r = \sum_{i=1}^{s} \frac{1}{c_i} $$ where all $c_i$ are different?

If true, are there any bounds on number of summands $s$ based on $n$ and $m$?

Answer by falagar for Is there a two-party multiplicative and additive secret sharing scheme ?

2010-07-21T14:32:17Z

Yes, there is such scheme. It was recently suggested by Craig Gentry.

Reference: "Fully Homomorphic Encryption Using Ideal Lattices" by Craig Gentry. http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.homoenc.html/$FILE/stocdhe.pdf

Answer by falagar for Number of subset sums

2010-07-21T09:10:09Z

There are $\binom{n}{k}$ ways to choose $k$ elements from $n$ elements. If we consider their sum it is "expected" to be equal to every element of the field with the same probability. Hence we get $\frac{1}{q}\binom{n}{k}$ for the number of solutions of $x_1 + x_2 + \cdots + x_k = s$. This is the first part of your question.

Now there are $\binom{q}{k}$ ways to choose $k$ different elements of the field. And $\frac{1}{q}$ of them have sum equal to $s$. In other words number of solutions of $x_1 + x_2 + \cdots + x_k = s$ is equal to $\frac{1}{q}\binom{q}{k}$.

If we choose random $D$ with $|D|=n$ every solution will have all $x_i \in D$ with the same probability $p$:

$$p = \frac{\binom{q-k}{n-k}}{\binom{q}{n}}$$

Hence the expected number of solutions is equal to $\frac{1}{q}\binom{q}{k} \cdot p$ which is equal to $\frac{1}{q}\binom{n}{k}$.

So the expected number of solutions is equal to $\frac{1}{q}\binom{n}{k}$.

Answer by falagar for Cesaro convergence implies weak convergence of a subsequence

2010-07-19T14:58:22Z

If we take $x_n = (-1)^n x$ then $x_n$ converges to $0$ in Cesaro sence. But no subsequence of $x_n$ converges weakly to $0$. $x_n$ is also a bounded sequence. Hence your statements seems wrong.

Answer by falagar for Guess a number with at most one wrong answer

2010-07-17T08:00:47Z

Yes, there is a way to guess a number asking 14 questions in worst case. To do it you need a linear code with length 14, dimension 10 and distance at least 3. One such code can be built based on Hamming code (see http://en.wikipedia.org/wiki/Hamming_code).

Here is the strategy.

Let us denote bits of first player's number as $a_i$, $i \in [1..10]$. We start with asking values of all those bits. That is we ask the following questions: "is it true that i-th bit of your number is zero?" Let us denote answers on those questions as $b_i$, $i \in [1..10]$.

Now we ask 4 additional questions:

Is it true that $a_{1} \otimes a_{2} \otimes a_{4} \otimes a_{5} \otimes a_{7} \otimes a_{9}$ is equal to zero? ($\otimes$ is sumation modulo $2$).

Is it true that $a_{1} \otimes a_{3} \otimes a_{4} \otimes a_{6} \otimes a_{7} \otimes a_{10}$ is equal to zero?

Is it true that $a_{2} \otimes a_{3} \otimes a_{4} \otimes a_{8} \otimes a_{9} \otimes a_{10}$ is equal to zero?

Is it true that $a_{5} \otimes a_{6} \otimes a_{7} \otimes a_{8} \otimes a_{9} \otimes a_{10}$ is equal to zero?

Let $q_1$, $q_2$, $q_3$ and $q_4$ be answers on those additional questions. Now second player calculates $t_{i}$ ($i \in [1..4]$) --- answers on those questions based on bits $b_j$ which he previously got from first player.

Now there are 16 ways how bits $q_i$ can differ from $t_i$. Let $d_i = q_i \otimes t_i$ (hence $d_i = 1$ iff $q_i \ne t_i$).

Let us make table of all possible errors and corresponding values of $d_i$:
position of error -> $(d_1, d_2, d_3, d_4)$

no error -> (0, 0, 0, 0)
error in $b_1$ -> (1, 1, 0, 0)
error in $b_2$ -> (1, 0, 1, 0)
error in $b_3$ -> (0, 1, 1, 0)
error in $b_4$ -> (1, 1, 1, 0)
error in $b_5$ -> (1, 0, 0, 1)
error in $b_6$ -> (0, 1, 0, 1)
error in $b_7$ -> (1, 1, 0, 1)
error in $b_8$ -> (0, 0, 1, 1)
error in $b_9$ -> (1, 0, 1, 1)
error in $b_{10}$ -> (0, 1, 1, 1)
error in $q_1$ -> (1, 0, 0, 0)
error in $q_2$ -> (0, 1, 0, 0)
error in $q_3$ -> (0, 0, 1, 0)
error in $q_4$ -> (0, 0, 0, 1)

All the values of $(d_1, d_2, d_3, d_4)$ are different. Hence we can find where were an error and hence find all $a_i$.

Finite groups with elements of order n

2010-07-14T05:24:20Z

Consider a finite group where all elements have the same order $n$. What could be said about such groups?

For $n=2$ it could be proved that such group is isomorphic to $(\mathbb{Z}/2\mathbb{Z})^k$. Could it be somehow generalized on case $n>2$?

EDIT: Surely the identity has order 1, so we have to exclude it.

Checking whether given binary operation is a group operation

2010-07-14T09:08:31Z

Given a binary function $f: [1..n] \times [1..n] \to [1..n]$ how to check that this operation is a group operation on $[1..n]$?

It's obvious that this can be done in $O(n^3)$ time just by checking all group properties. The most time-expensive property is associativity. Also it's clear that it could not be done faster than $O(n^2)$ time since you should at least examine all values $f(i,j)$.

The question is if there is any algorithm to solve this problem in time faster than $O(n^3)$?

Finite nonabelian groups of odd order

2010-07-12T14:06:10Z

For every even $n$ there exists nonabelian group. As example of such group we can take dihedral group.

The question is about odd $n$. For some of them there are no nonabelian groups of order $n$ (for example, if $n$ is prime then the group of order $n$ is cyclic and hence abelian).

For what odd $n$ are there known examples of nonabelian finite groups of order $n$?

Answer by falagar for Interchanging summations

2010-07-13T08:49:46Z

All the terms in this summation are positive, so you can change the order. The result wouldn't change.

The summation is done over all pairs $(k, j)$ with $j \le k$. The first summation first sums over all $k$ and after that over all $j$, the second one --- first sums over all $j$ and after that over all $k$.

Distinct numbers in multiplication table

2010-07-13T05:37:54Z

Consider multiplication table for numbers $1,2,\cdots, n$. How many different numbers are there? That is how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there?

I'm interested in a formulae or an algorithm to calculate this number in time less than $O(n^2)$.

Answer by falagar for Interesting applications of max-flow and linear programming

2010-07-12T14:23:22Z

Another interesting application of LP is finding Nash equilibrium for a two player zero-sum game.

http://en.wikipedia.org/wiki/Zero-sum_game#Solving

Approximation with continuous functions

2010-07-10T05:58:43Z

Is it true that for every function $\mathbb{R} \to \mathbb{R}$ there exists a sequence of continuous functions $f_n(x): \mathbb{R} \to \mathbb{R}$ such that for any $x \in \mathbb{R}$ $f_n(x)$ converges to $f(x)$?

I started with characteristic function of rationals and tried to find corresponding sequence and got stuck. So additional question if this statement is true for this function.

Math and music theory

2010-07-12T06:20:33Z

Are there any interesting connections between math objects (theorems, definitions, constructions) and music theory?

Answer by falagar for Algorithm for determining if a path exists in a graph or if not, the closest edit distance.

2010-07-10T13:40:46Z

If graph is acyclic you can use some sort of dynamic programming. Let $a_{u,k}$ be the best distance you can get if you start from vertex $u \in G$ and consider only $k$ last vertices of your given path.

It's quite straightforward how to calculate all $a_{u,k}$ based on all values of $a_{u',k'}$ with $u'$ "after" $u$ and $k' < k$: you just iterate over all edges going from vertex $u$.

This approach works in $O(|G| \times strlen)$ time.

Answer by falagar for Arithmetic fixed point theorem

2010-07-10T12:54:50Z

Another approach, I suppose, is to consider this as a kind of Cantor's diagonal argument. If you write a table with rows correspond to formula and columns correspond to integers then $sub([F],[t])=[F_v(t)]$ is just a formulae in $[F]$ row and $t$ column. Now, following Cantor's diagonal argument, you might want to consider diagonal of this table, which is $sub(v,num(v))$ and augment it somehow. Here is there $F$ comes in - you apply it to the diagonal and get $H(v)=F_v(sub(v,num(v)))$. Why should you? I don't know exactly. But it's similar to standard Cantor's argument.

Hence, $H(v)$ is a formulae with the following property: for every formulae $T(v)$ there exist $n$ such that $H(n) \Leftrightarrow F(T(n))$ (because of diagonal argument --- take row number $[T]$ and intersect it with diagonal). That's why we can take $n = [T]$.

Hence, if we take $T = H$, and $n = [T] = [H]$ we would get what we need.

Unbounded linear operator defined on $l^2$

2010-07-09T09:08:35Z

Let $l^2$ be a Hilbert space of infinite sequences $(z_0, z_1, \cdots)$ with finite $\sum_{i=0}^{\infty} |z_i|^2$.

Are there any simple example of unbounded linear opearator $T: l^2 \to l^2$ with $D(T)=l^2$?

Answer by falagar for unique integer partitions

2010-07-09T09:29:39Z

If you need an algorithm to calculate this number, you can use the following. Let $a_{nk}$ be an answer to your question, then it's not hard to prove that $a_{nk} = a_{n,k-1} + a_{n - k, k}$. So you can fill in the table of all $a_{nk}$ using this formulae.

Comment by falagar

2010-08-13T11:54:01Z

@pravesh, in your example $de < p$.

Comment by falagar

2010-08-13T11:52:15Z

And I don't know if there exists faster solution.

Comment by falagar

2010-08-13T11:50:31Z

Is $R(p)$ the optimal gain in putting $p$ balls considering all the buckets? If so then I don't understand your formula. If you have put $i$ balls into $k$-th bucket you can't use this bucket any more.

Comment by falagar

2010-08-13T10:01:23Z

What if $l=m=1$ and $N > p+1$? Then you take partitions $p=p$ and $p+1=p+1$ and there are no subsets with equal sums.

Comment by falagar

2010-08-13T09:50:56Z

Yes, if $k$ is fixed and we are interested only how time complexity depends on $n$ then both algorithms have the same complexity. They actually differ by a factor of $k!$.

Comment by falagar

2010-08-13T09:36:27Z

The number of $k$-tuples with distinct elements is $\frac{n!}{(n-k)!}$ which for big $k$ is much more than the number of subsets with at most $k$ elements. For example if $n=k$ then this algorithm works in time $O(n^2 2^n)$ and enumerating algorithm in time $O(n!)$.

Comment by falagar

2010-07-26T09:46:47Z

There are too many prime numbers between $n_1$ and $n_2$ in those cases. Even for the first case there are about $10^12$ primes.

Comment by falagar

2010-07-23T13:10:36Z

I can suggest en.wikipedia.org/wiki/Differential_entropy

Comment by falagar

2010-07-23T08:21:50Z

tdnoe, thank you for your comment! It indeed was a typo.

Comment by falagar

2010-07-23T08:18:11Z

Thank you for your comments! I think we should close the question.

Comment by falagar

2010-07-21T10:45:26Z

I think that I don't use the assumption that q is comprime to k.

Comment by falagar

2010-07-20T13:06:25Z

Actually I want proof that is niether of two mentioned in the question. By "a simple non-analytic proof" I mean a proof that doesn't use any of classical analysis.

Comment by falagar

2010-07-14T11:30:18Z

Integer factorization can be converted into decision problem: given $n$ and $k$ return YES if $k$-th bit of the smallest prime divisor of $n$ is equal to $1$.

Comment by falagar

2010-07-14T06:10:12Z

Do you need just EXPTime-Complete problem? If so there is one in wikipedia: en.wikipedia.org/wiki/EXPTIME. Given a (determinister for first question, nondeterministic for the second) Turing machine and time T decide wheter it halts after T steps.

Comment by falagar

2010-07-14T05:59:50Z

Well, I understand now that $n$ must be prime and group might be nonabelian. So there are no straitforward generalizations of case $n=2$. Originally, I was looking for the statement like '... then the group is isomorphic to such or such group'. Now I think there are no such classification and the question is closed.