All Questions
203 questions
36
votes
3
answers
7k
views
Distinct numbers in multiplication table
Consider the multiplication table for the numbers $1,2,\dots, 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 ...
- 2,821
52
votes
4
answers
17k
views
How hard is it to compute the number of prime factors of a given integer?
I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.
...
- 2,416
47
votes
1
answer
3k
views
improving known bounds for Pierce expansions; cash prize
Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...
- 3,028
44
votes
11
answers
26k
views
Algorithm for finding the volume of a convex polytope
It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
- 441
7
votes
1
answer
760
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
- 123
21
votes
5
answers
3k
views
How can you find an integer coefficient polynomial knowing its values only at a few points (but requiring the coefficients be small)?
Example: How can you guess a polynomial $p$ if you know that $p(2) = 11$? It is simple: just write 11 in binary format: 1011 and it gives the coefficients: $p(x) = x^3+x+1$. Well, of course, this ...
- 24.9k
22
votes
9
answers
21k
views
Is there an algorithm to solve quadratic Diophantine equations?
I was asked two questions related to Diophantine equations.
Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all ...
- 223
17
votes
2
answers
4k
views
Optimizing the condition number
Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns $...
- 96.4k
69
votes
2
answers
25k
views
Does there exist a complete implementation of the Risch algorithm?
Is there a generally available (commercial or not) complete implementation of the Risch algorithm for determining whether an elementary function has an elementary antiderivative?
The Wikipedia article ...
- 82.6k
47
votes
15
answers
29k
views
What are the applications of hypergraphs?
Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
30
votes
3
answers
3k
views
Is it decidable whether or not a collection of integer matrices generates a free group?
Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
- 18.7k
24
votes
4
answers
36k
views
Finding a cycle of fixed length
Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph?
All I know is that Alon, Yuster and Zwick use a technique called "color-coding",
which has a ...
- 1,250
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
11
votes
4
answers
12k
views
How to find all integer points on an elliptic curve?
How can I determine the integer points of a given elliptic curve if I know its rank and its torsion group?
I read same basic books on elliptic curves but as a non-professional I didn't understand ...
7
votes
1
answer
466
views
Algorithm for comparing $x + y \cdot \log(z)$ for $x,y,z$ rational?
I'm playing with some methods of comparing two real numbers of the form $x + y \log(z)$, where $x,y,z$ are rational numbers and $z$ is positive. There are various estimates on irrationality measures ...
- 13.3k
7
votes
1
answer
799
views
Is equality of terms for "real" numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?
If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
- 125
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
5
votes
3
answers
411
views
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
3
votes
1
answer
327
views
LP Constraints for Connected Subgraphs of Fixed Size
Question:
how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?
...
- 13.2k
64
votes
1
answer
5k
views
How to be rigorous about combinatorial algorithms?
1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...
- 33.8k
58
votes
2
answers
18k
views
How fast can we *really* multiply matrices?
Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). ...
- 15.5k
46
votes
7
answers
13k
views
What is the time complexity of computing sin(x) to t bits of precision?
Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...
- 6,694
41
votes
5
answers
15k
views
Computing the Galois group of a polynomial
Does there exist an algorithm which computes the Galois group of a polynomial
$p(x) \in \mathbb{Z}[x]$? Feel free to interpret this question in any reasonable manner. For example, if the degree of $p(...
- 8,298
33
votes
3
answers
6k
views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
- 19.6k
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
27
votes
1
answer
678
views
Decidability of equality of expressions built using 1,+,-,*,/,^
Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
- 371
20
votes
2
answers
25k
views
Partitioning a polygon into convex parts
I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.
I know almost nothing about this subject, so I've been searching on Google ...
- 201
19
votes
3
answers
3k
views
When are (finite) simplicial complexes (smooth) manifolds?
Hi,
is there an algorithm that determines if a given simplicial complex is
a.) a manifold
b.) a smooth manifold
c.) homotopy equivalent to a manifold
d.) a real algebraic variety
?
- 949
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
17
votes
9
answers
3k
views
Where on the internet I can find a database of graphs?
I am studying graph algorithms.
I need a database of graphs on which I can test my algorithms.
Where can I find a reliable database of graphs of all kinds?
Thanks!
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
16
votes
2
answers
789
views
Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)
Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$.
Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix ...
- 525
14
votes
2
answers
748
views
Checking whether given binary operation is a group operation
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 ...
- 2,821
13
votes
3
answers
890
views
Effective algorithm to test positivity
Let $f(x_1,\ldots, x_n)$ be a real polynomial in several variables. Is there an effective algorithm to test whether $f$ is positive (or nonnegative) on the whole of ${\mathbb{R}}^n$?
user2529
11
votes
3
answers
2k
views
Mertens' function in time $O(\sqrt x)$
This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...
- 9,114
11
votes
2
answers
3k
views
Algorithm for embedding a graph with metric constraints
Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
- 7,857
10
votes
1
answer
682
views
Building a polyhedron from areas of its faces
Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
- 6,819
10
votes
1
answer
582
views
Can Tarski decide constructibility in elementary geometry?
Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction?
The answer does ...
- 11.1k
9
votes
1
answer
277
views
Algorithmically handling the Spin groups in larg(ish) dimensions
Question: Is there a reasonably efficient algorithmic representation of $\mathit{Spin}_n$? By this I mean, a way to store its elements and operate on them (multiply, inverse, maybe compute ...
- 32.5k
8
votes
1
answer
1k
views
Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?
Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...
- 13.4k
7
votes
4
answers
4k
views
Generating random curves with fixed length and endpoint distance
Are algorithms already known, that generate (arbitrarily good approximations of) random curves, w.l.o.g. with unit length, and joining endpoints $(0,0)$ and $(\alpha,0)$ with $\alpha \lt1$ given?
The ...
- 13.2k
7
votes
2
answers
679
views
What is wrong with this deterministic algorithm efficiently generating large primes?
According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. ...
- 25.4k
6
votes
2
answers
453
views
Minimum number of unit fractions to sum up a given positive rational
For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$, see this article by Paul Erdös and Sherman Stein (...
- 48.8k
6
votes
1
answer
1k
views
Exact arithmetic for real algebraic numbers
There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms
in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...
- 9,132
6
votes
5
answers
4k
views
Package for the Closest Vector Problem (CVP)?
Let $A$ be a positive definite, real $n \times n$ matrix. This defines a norm on $\mathbb{R}^n$. Now I have a given point $p \in \mathbb{R}^n$ and I want to find the lattice point $x \in \mathbb{Z}^n$ ...
- 3,031
5
votes
1
answer
453
views
an algebraic variety for a boolean circuit
There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$.
I mean there is polynomial reduction $F$ such that for every boolean ...
- 2,576
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
5
votes
2
answers
580
views
Box stacking problem
Real world problem alert: I am moving from my house to another one, and the problem below arised when I tried to fit some little boxes of various shapes into a large box:
We are given a positive ...
- 48.8k
4
votes
1
answer
8k
views
Detection of Redundant Constraints
Suppose I pose the following query to a constraint logic programming
system:
?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.
Are there systems that would recognize the last inequality as
...
Countably Infinite