# Tagged Questions

**27**

votes

**0**answers

2k views

### A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...

**24**

votes

**2**answers

2k views

### Projective Plane of Order 12

I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can ...

**20**

votes

**6**answers

2k views

### What heuristic evidence is there concerning the unboundedness or boundedness of Mordell-Weil ranks of elliptic curves over $\Bbb Q$?

Some experts have a hunch that for any nonnegative integer $r$ there are infinitely many elliptic curves over $\Bbb Q$ with Mordell-Weil rank at least $r$.
The best empirical evidence for this hunch ...

**17**

votes

**2**answers

2k views

### Walking to infinity on the primes: The prime-spiral moat problem

It is an unsolved problem to decide if it is possible to "walk to infinity" from the origin
with bounded-length steps, each touching a Gaussian prime as a stepping stone.
The paper by Ellen Gethner, ...

**33**

votes

**2**answers

2k views

### Euler and the Four-Squares Theorem

There are several questions in the Euler-Goldbach correspondence that
I am unable to answer. Sometimes it does not take very much: in his
letter to Goldbach dated June 9th, 1750, Euler conjectured
...

**2**

votes

**1**answer

934 views

### The importance of Poincare Conjecture or SPC4?

As well known, Perelman proved Poincare conjecture by proving Thurston's Geometrization conjecture.
Somebody says that we can understand part of the universe from Poincare conjecture.
As a purely ...

**13**

votes

**2**answers

1k views

### Detecting almost-primes quickly

There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a number is the product ...

**21**

votes

**0**answers

1k views

### Finite-dimensional subalgebras of $C^\star$-algebras

Let $A$ be a unital $C^\star$-algebra and let $a_1,\dots,a_n$ be a finite list of normal elements in $A$ which (together with their adjoints) generate a norm-dense $\star$-subalgebra $B \subset A$. ...

**11**

votes

**2**answers

2k views

### What impact would P!=NP have on the characterization of BQP?

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...

**12**

votes

**0**answers

2k views

### How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version.
Here are Vinay Deolalikar's paper, and Richard Lipton's first post ...

**4**

votes

**1**answer

606 views

### Reconstruction Conjecture: Group theoretic formulation

As we read from wiki, informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs.
Is there a group-theoretic formulation of this ...

**8**

votes

**3**answers

1k views

### Conjugacy classes and reduced group $C^*$-algebra of an amenable group

The reduced $C^*$-algebra of a non-abelian free group $G$ has a unique trace. Hence, there is no chance to separate conjugacy classes of group elements using traces on $C^\star_{red} G$. On the other ...

**11**

votes

**3**answers

2k views

### Permute Wada Lakes keeping the coastline intact? (still open in dim >2)

Wada Lakes are three disjoint open subsets of $\mathbb R^2$ with common boundary. Originally they were constructed by hand, but they also arise naturally in the real life, that is, theory of dynamical ...

**16**

votes

**1**answer

1k views

### Are all primes in a PAP-3?

Van der Corput [1] proved that there are infinitely many arithmetic progressions of primes of length 3 (PAP-3). (Green & Tao [2] famously extended this theorem to length $k$.)
But taking this in ...

**29**

votes

**3**answers

4k views

### Can we cover the unit square by these rectangles?

The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.
It is easy to show that
$$\sum_{1 \leq k } ...

**0**

votes

**1**answer

1k views

### Existence of a pseudo-polynomial time algorithm for a counting problem.

Let T={1,...,n} be a set of tasks. Each task i has associated a non negative processing time p_i and a deadline d_i. A feasible schedule of the tasks consists of a permutation of n elements pi, such ...

**12**

votes

**0**answers

1k views

### Razborov's response to Almost Natural Proofs

This post is about Natural Proofs barrier in computational complexity.
There are two recent papers related to this. They are:
Amplifying lower bounds by means of self-reducibility by Eric Allender ...

**3**

votes

**1**answer

724 views

### Cyl(E) = Borel(E) for E non-reflexive Grothendieck Banach space

This is sort of a follow-up to Borel(X) = \sigma(X') for X non-separable
PROBLEM: Given a Banach space $E$ over $\mathbb{K} \in \{\mathbb{C}, \mathbb{R}\}$ that has the Grothendieck property. ...

**12**

votes

**6**answers

2k views

### Smallest area shape that covers all unit length curve

On a euclidean plane, what is the minimal area shape S, such that for every unit length curve, a translation and a rotation of S can cover the curve.
What are the bounds of the shape's area if this ...

**17**

votes

**6**answers

2k views

### Question on consecutive integers with similar prime factorizations

Suppose that $n=\prod_{i=1}^{k} p_i^{e_i}$ and $m=\prod_{i=1}^{l} q_i^{f_i}$ are prime factorizations of two positive integers $n$ and $m$, with the primes permuted so that $e_1 \le e_2 \cdots \le ...

**38**

votes

**13**answers

5k views

### What are some of the big open problems in 3-manifold theory?

From what I understand, the geometrization theorem and its proof helped to settle a lot of outstanding questions about the geometry and topology of 3-manifolds, but there still seems to be quite a lot ...

**5**

votes

**2**answers

594 views

### Lower bounds (or less) for the period of \sqrt(D) and related sequences.

This is a continuation of
Lower bounds for period length of continued fraction of square root
which is a continuation of
Upper bound of period length of continued fraction representation of very ...

**20**

votes

**2**answers

2k views

### Curves of constant curvature on S^2

Most probably this is a well known question.
Consider $S^2$ with a Riemannian metric. I would like to ask what is known about the structure of the set of simple (without self-intersections) closed ...

**47**

votes

**8**answers

6k views

### The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
Let $C$ be a ...

**11**

votes

**2**answers

2k views

### Does listing the prime factors always stop?

Take a natural number's prime factors and list them increasingly and repeating them according to multiplicity. Concatenate their decimal (or in any base) representation to get a new number and repeat ...

**24**

votes

**4**answers

2k views

### Is Lebesgue's “universal covering” problem still open?

The following problem has been attributed to Lebesgue. Let "set" denote any subset of the Euclidean plane. What is the greatest lower bound of the diameter of any set which contains a subset congruent ...

**8**

votes

**1**answer

1k views

### Smallest dilation of a quadrilateral?

What is the smallest dilation of a quadrilateral in $\mathbb{R}^d$?
This may be an open problem, which I know is verboten on MO.
So my question is: Is this indeed open?
It will take me some time to ...

**7**

votes

**5**answers

2k views

### List of recently solved mathematical problems

I'm looking for a news site for Mathematics which particularly covers recently solved mathematical problems together with the unsolved ones. Is there a good site MO users can suggest me or is my only ...

**57**

votes

**0**answers

3k views

### Volumes of Sets of Constant Width in High Dimensions

Background
The n dimensional Euclidean ball of radius 1/2 has width 1 in every direction. Namely, when you consider a pair of parallel tangent hyperplanes in any direction the distance between them ...

**6**

votes

**6**answers

607 views

### Statements reliant on conjectures

There are lots of statements that have been conditionally proved on the assumption that the Riemann Hypothesis is true.
What other conjectures have a large number of proven consequences ?

**39**

votes

**4**answers

6k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...

**8**

votes

**1**answer

478 views

### Periodic Automorphism Towers

In Scott's classic textbook on Group Theory, he asks:
Suppose that $G$ is a finite group. Is the sequence of isomorphism types
of the groups $Aut^{(n)}(G)$ for $n \in \mathbb{N}$ eventually periodic?
...

**42**

votes

**2**answers

3k views

### Polynomials having a common root with their derivatives

Here is a question someone asked me a couple of years ago. I remember having spent a day or two thinking about it but did not manage to solve it. This may be an open problem, in which case I'd be ...

**49**

votes

**6**answers

9k views

### Is Thompson's Group F amenable?

Last year a paper on the arXiv (Akhmedov) claimed that Thompson's group $F$ is not amenable, while another paper, published in the journal "Infinite dimensional analysis, quantum probability, and ...

**17**

votes

**1**answer

1k views

### Coiling Rope in a Box

What is the longest rope length L of radius r that can fit into a box?
The rope is a smooth curve with a tubular
neighborhood of radius r, such that the rope does not
self-penetrate. For an open ...

**33**

votes

**6**answers

2k views

### Can we color Z^+ with n colors such that a, 2a, …, na all have different colors for all a?

For example for n=2 coloring odd numbers red, numbers of the form 4k+2 blue and so on works.
This problem was posed in the KoMaL for n+1 prime, if I know well by Geza Kos. I verified it for all ...

**9**

votes

**0**answers

725 views

### Dissecting trapezoids into triangles of equal area

[Lightly edited for copy and proper formatting of mathematics. -- Pete L. Clark]
The Background: Let $T$ be a trapezoid. Sherman Stein, using valuation theory, showed that if $T$ is dissectible into ...

**18**

votes

**2**answers

734 views

### Ramsey multiplicity

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ ...

**1**

vote

**0**answers

103 views

### Square powers of hemicontinuous operators

Let H be an infinite dimensional real Hilbert space.
A [not necessarily linear] mapping of H into itself is said to be hemicontinuous if it is continuous from each line
segment of H to the weak ...

**16**

votes

**3**answers

1k views

### Cutting convex sets

Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.
Can one cut every bounded convex set of the Euclidean plane into an arbitrary number ...

**6**

votes

**1**answer

735 views

### Current status of Bloch Constant and Landau Constant bounds

The Bloch constant B (based on a theorem introduced by André Bloch in 1925 on the maximum radius of a one-to-one disk in the image of a normalized analytic function of the unit disk, see for instance ...

**9**

votes

**2**answers

1k views

### Is there an uncountable, non-discrete, Hausdorff Toronto space?

We call a topological space $X$ a Toronto space if for any subspace $Y \subseteq X$ such that $Y$ and $X$ have the same cardinality it follows that $Y$ is homeomorphic to $X$.
Does anybody know what ...

**7**

votes

**2**answers

733 views

### Covers of Riemann surfaces which become arbitrary close in Teichmuller space

Suppose $S$ and $S'$ are two compact Riemann surfaces of genus $g$. Does there exist a sequence of genera $g_i \to \infty$ and covers $S_i, S_{i}'$ of $S,S'$, both of genus $g_i$, such that ...

**21**

votes

**4**answers

9k views

### Does pi contain 1000 consecutive zeroes (in base 10)?

The motivation for this question comes from the novel Contact by Carl Sagan. Actually, I haven't read the book myself. However, I heard that one of the characters (possibly one of those aliens at ...

**310**

votes

**2**answers

24k views

### Polynomial bijection from $\mathbb Q\times\mathbb Q$ to $\mathbb Q$?

Is there any polynomial $f(x,y)\in{\mathbb Q}[x,y]{}\ $ such that $f:\mathbb{Q}\times\mathbb{Q} \rightarrow\mathbb{Q}$ is a bijection?

**58**

votes

**2**answers

3k views

### Is it known that the ring of periods is not a field?

I have just learned here that we know numbers that are not periods; is it known meanwhile that the ring of periods is not a field? I know that it is conjectured that $1/\pi$ is not a period, but the ...

**6**

votes

**1**answer

460 views

### distribution of degree of minimum polynomial for eigenvalues of random matrix with elements in finite field

This is an attempt to extend the current full fledged random matrix theory to fields of positive characteristics. So here is a possible setup for the problem: Let $A_{n,p}$ be an $n \times n$ matrix ...

**48**

votes

**0**answers

2k views

### 2, 3, and 4 (a possible fixed point result ?)

The question below is related to the classical Browder-Goehde-Kirk fixed point theorem.
Let $K$ be the closed unit ball of $\ell^{2}$, and let $T:K\rightarrow K$
be a mapping such that $\Vert ...

**75**

votes

**4**answers

4k views

### If $2^x $and $3^x$ are integers, must $x$ be as well?

I'm fascinated by this open problem (if it is indeed still that) and every few years I try to check up on its status. Some background: Let $x$ be a positive real number.
If $n^x$ is an integer for ...

**53**

votes

**3**answers

2k views

### Does linearization of categories reflect isomorphism?

Given a category $C$ and a commutative ring $R$, denote by $RC$ the $R$-linearization: this is the category enriched over $R$-modules which has the same objects as $C$, but the morphism module between ...