All Questions
1,297 questions
113
votes
7
answers
8k
views
Is the set $ AA+A $ always at least as large as $ A+A $?
Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
- 1,498
78
votes
12
answers
12k
views
Why aren't representations of monoids studied so much?
It seems to me like every book on representation theory leaps into groups right away, even though the underlying ideas, such as representations, convolution algebras, etc. don't really make explicit ...
- 2,392
63
votes
5
answers
10k
views
Jean Bourgain's relatively lesser known significant contributions
Jean Bourgain passed away on December 22, 2018.
A great mathematician is no longer with us.
Terry Tao has blogged about Bourgain's death and mentioned some of his more recent significant contributions,...
59
votes
2
answers
4k
views
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
I am currently working on a proof that would need to use the following theorem that I cannot prove:
"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
- 643
58
votes
3
answers
6k
views
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
- 897
51
votes
3
answers
3k
views
Is each squared finite group trivial?
A semigroup $S$ is defined to be squared if there exists a subset $A\subseteq S$ such that the function $A\times A\to S$, $(x,y)\mapsto xy$, is bijective.
Problem: Is each squared finite group ...
- 41.9k
44
votes
4
answers
2k
views
Sets of unit fractions with sum $\leq 1$
Consider a set of fractions $\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\right\}$. How many subsets of this set have sum at most 1? I'm interested in the asymptotics of this number.
...
- 5,590
42
votes
5
answers
4k
views
What are the main structure theorems on finitely generated commutative monoids?
I should read J. C. Rosales and P. A. García-Sánchez's book Finitely Generated Commutative Monoids and L. Redei's book The Theory of Finitely Generated Commutative Semigroups. I haven't. But here's ...
- 22.3k
41
votes
2
answers
3k
views
Is number of different sums monotone?
Suppose you have a set $S$ consisting of $n$ different integers.
Let $$W_k = \#\biggl\{x\in\Bbb Z\colon \text{there exists } T \subseteq S,\, \#T=k,\, \sum_{a \in T} a = x\biggr\}.$$
My question is: ...
- 673
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 38.6k
35
votes
3
answers
2k
views
Lagrange four squares theorem
Lagrange's four square theorem states that every non-negative integer is a sum of squares of four non-negative integers. Suppose $X$ is a subset of non-negative integers with the same property, that ...
- 1,651
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
- 703
33
votes
0
answers
2k
views
Is there a (discrete) monoid M injecting into its group completion G for which BM is not homotopy equivalent to BG?
For a (discrete) monoid $M$, the classifying space $BM$ is the
geometric realization of the nerve of the one object category whose
hom-set is $M$. (This definition gives the usual classfiying space
...
- 5,309
32
votes
5
answers
9k
views
How many binary operations are associative?
Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...
- 151k
32
votes
2
answers
3k
views
The Erdős–Turán conjecture or the Erdős conjecture?
This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics:
Conjecture: If $A\subset \mathbb{N}$ and $$\...
- 11.4k
29
votes
1
answer
1k
views
Is the Golomb countable connected space topologically rigid?
The Golomb space $\mathbb G$ is the set of positive integers endowed with the topology generated by the base consisting of the arithmetic progressions $a+b\mathbb N_0$ with relatively prime $a,b$ and $...
- 41.9k
28
votes
3
answers
969
views
Ordering subsets of the cyclic group to give distinct partial sums
Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,...
- 281
27
votes
13
answers
4k
views
Homological algebra for commutative monoids?
Homological algebra for abelian groups is a standard tool in many fields of mathematics. How much carries over to the setting of commutative monoids (with unit)? It seems like there is a notion of ...
- 27.5k
27
votes
1
answer
2k
views
Is every real number in [0,1] a product of three (or more) Cantor set's numbers?
It is well known that every number $x$ in the unit interval $[0,1]$ is the arithmetic mean of two elements of the (triadic) Cantor set $C$. The way to see it I like the most: the Cantor set is the ...
- 60.5k
27
votes
1
answer
3k
views
Monochromatic triangles in every two-coloring of the plane?
An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...
- 7,857
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
- 109k
26
votes
3
answers
2k
views
long enough interval of integers to solve a simultaneous congruence
Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ ...
- 285
26
votes
1
answer
1k
views
probability of zero subset sum
Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not).
Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
- 37.7k
26
votes
0
answers
910
views
Which sets of roots of unity give a polynomial with nonnegative coefficients?
The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...
- 1,513
25
votes
3
answers
1k
views
What spaces $X$ do have $\text{End}(X) \cong \text{End}(\mathbb{R})$?
This is a follow-up on the following question. Let $\text{End}(X)$ denote the endomorphism monoid of a topological space $X$ (that is, the collection of all continuous maps $f:X\to X$ with composition)...
- 48.9k
25
votes
2
answers
1k
views
The number of polynomials on a finite group
A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. ...
- 41.9k
25
votes
1
answer
2k
views
Arithmetic Progressions of Squares
Fermat may or may not have known that there are 3-term arithmetic progressions of squares (like $1^2, 5^2, 7^2$, and that there are no 4-term APs. Murky history aside, Keith Conrad has two pleasant ...
- 9,756
24
votes
2
answers
3k
views
What is the minimal density of a set A such that A+A = N?
Thinking about the four square theorem and related questions, I found myself wondering: What is the minimal density of a set $A \subset \{0, 1, 2, ... \}$ such that $A + A = \mathbb{N}$?
What I know:
...
- 1,633
24
votes
3
answers
3k
views
Non-abelian Grothendieck group
By general nonsense the forgetful functor from groups to monoids has a left adjoint. It maps a monoid $(X,\cdot,1)$ to the free group on $\{\underline{x} : x \in X\}$ modulo the relations $\underline{...
- 63.1k
24
votes
4
answers
3k
views
What is the shortest route to Roth's theorem?
Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
- 7,013
24
votes
3
answers
2k
views
Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?
The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak ...
- 2,719
24
votes
5
answers
2k
views
Lie groups vs Lie monoids
Does there exist a well developed theory of a class of objects which might rightfully be called Lie monoids? By this I mean with axioms similar to those of Lie groups, but with the axiomatic existence ...
- 2,099
24
votes
2
answers
7k
views
EGZ theorem (Erdős-Ginzburg-Ziv)
Erdős, Ginzburg and Ziv prove the following:
Let $n \geq 1$ and $a_1,\ldots, a_{2n-1}\in \mathbb{Z}$. There exist distinct $i_1,\ldots , i_n$
such that
$$
a_{i_1} + \cdots + a_{i_n} \equiv 0 \pmod{n}....
- 2,829
23
votes
3
answers
3k
views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
- 323
23
votes
1
answer
801
views
integers which are sums of binomial coefficients: $\sum_i {n \choose k_i}$
Let $n$ be an integer. For $S$ a subset of $\{0,\dots,n\}$, define
$$m(S) = \sum_{k \in S} {n \choose k}.$$
Let $M_n$ be the set of integers of the form $m(S)$ for all sets $S \subset \{0,\dots,n\}$. ...
- 26k
22
votes
2
answers
977
views
Mapping from a finite index subgroup onto the whole group
Dear All,
here is the question:
Does there exist a finitely generated group $G$ with a proper subgroup $H$ of finite index, and an (onto) homomorphism $\phi:G\to G$ such that $\phi(H)=G$?
My guess ...
- 1,437
22
votes
2
answers
1k
views
Toposes (topoi) as classifying toposes of groupoids
A famous theorem of Joyal and Tierney says that each Grothendieck topos is equivalent to the classifying topos of a localic groupoid. I believe that Butz and Moerdijk have shown that if the topos has ...
- 38.6k
21
votes
2
answers
3k
views
Integer matrices with no integer eigenvalues
Let $$A = \begin{pmatrix} 3&1 \\ 0&1 \end{pmatrix}$$ and $$B = \begin{pmatrix} 1&0\\ 1&2 \end{pmatrix}$$ I want to show that the only elements of the semigroup generated by $A$ and $B$...
- 1,045
21
votes
1
answer
740
views
Does $A-A=\mathbb Q$ hold for $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$?
Let $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$. Then
$$A-A:=\{a-b:\ a,b\in A\}=\{u^4+v^4-x^4-y^4:\ u,v,x,y\in\mathbb Q\}.$$
Motivated by Question 415482, here I ask the following question.
Question. Is it true ...
- 15.6k
21
votes
1
answer
759
views
Extending $\Bbb N$ to a semiring with isomorphic additive and multiplicative structure
Seen $(\Bbb N,+,\cdot)$ as a semiring, is it possible to extend it to a semiring $(R,+,\cdot)$ so that the additive and multiplicative monoids become isomorphic? This means there is some monoid-...
- 13.6k
21
votes
1
answer
638
views
Grothendieck group of the Fibonacci monoid
Let's denote the Fibonacci numbers by $F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n \; \forall n \ge 0$. According to Zeckendorf's theorem, every positive integer can be represented uniquely as the sum of some (at ...
- 1,543
21
votes
1
answer
773
views
Avoiding multiples of $p$
Let $p$ be a prime number and $P=\{1,2,...,p-1\}$
In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$
only when we sum the last summand?
For ...
- 3,866
20
votes
3
answers
1k
views
Size of set of integers with all sums of two distinct elements giving squares
Are there arbitrarily large sets $\mathcal S=\{a_1,\ldots,a_n\}$ of strictly positive integers such that all sums $a_i+a_j$ of two distinct elements in $\mathcal S$ are squares?
Considering subsets in ...
- 17.9k
20
votes
3
answers
1k
views
A sumset inequality
A friend asked me the following problem:
Is it true that for every $X\subset A\subset \mathbb{Z}$, where $A$ is finite and $X$ is non-empty, that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A|}?$$
Here ...
- 11.4k
20
votes
4
answers
3k
views
Arithmetic progressions inside polynomial sets
There are at most 3 perfect squares in arithmetic progression (Fermat, Euler). It was shown in [1] that if $n>2$ there are no three term arithmetic progression consisting of nth powers.
Take a non-...
- 566
19
votes
3
answers
1k
views
The sum of integers being a bijection
What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...
- 52.3k
19
votes
3
answers
1k
views
Decomposing a finite group as a product of subsets
My friend Wim van Dam asked me the following question:
For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? ...
- 9,823
19
votes
3
answers
1k
views
Can nonabelian groups be detected "locally"?
Suppose $m,n\geq 2$ are two integers. Is it true that for every sufficiently large nonabelian group $G$, one can find a set $A\subset G$, with $|A|=n$, so that $|A^m| >\binom{n+m-1}{m}$?
(Edit) ...
- 85.6k
19
votes
4
answers
865
views
Size of sets with complete double
Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...
- 30.5k
19
votes
3
answers
1k
views
An “Average” Erdős–Turán conjecture
Right, so the Erdős–Turán conjecture for additive bases (of order 2) says, with the usual notations, that $\sup r_B (n) = \infty$. Let’s look instead at the average number of representations, i.e.: ...
- 983