All Questions
1,297 questions
0
votes
1
answer
60
views
Is there a characterization of monoids that distribute over each other?
Let $(M, e_1, \times_1, e_2, \times_2)$ be an algebraic structure such that
$(M, e_1, \times_1)$ and $(M, e_2, \times_2)$ are monoids
$x \times_1 (y \times_2 z) = (x \times_1 y) \times_2 (x \times_1 ...
- 631
4
votes
1
answer
270
views
Maximum density of sum-free sets with respect to Knuth's "addition"
A subset $S\subseteq\mathbb{N}$ is said to be sum-free if whenever $s,t\in S$, then $s+t\notin S$. For instance the set of odd numbers is sum-free and has (lower and upper) asymptotic density 1/2.
...
- 9,720
4
votes
1
answer
162
views
Lower bounding a sumset quantity
Given $A,B \subset[0,...,d]^n$ such that $A \cap B = \phi$. Can we show
$$ |(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|))$$
where $2A = A+A, 2B = B+B$ and we are taking the ...
- 341
4
votes
0
answers
137
views
Lemma in Roth's Theorem for Primes
I am reading Ben Green's paper Roth's Theorem in the Primes and I don't follow the proof of Lemma 6.1. I am not sure where the fact there are no more than $n^{3/4}$ elements $x\in A_0$ with $x\leq n^{...
- 105k
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 ...
- 1,567
5
votes
0
answers
542
views
A problem on additive combinatorics in right-ordered groups
In a paper Small doubling in ordered groups: generators and structure it is proven in Lemma 4 page no. 598 that:
Let $G$ be an ordered group. Let $S$ be a finite subset of $G$ with at least two ...
11
votes
0
answers
427
views
Is there a theory of completions of semirings similar to $I$-adic completions of rings?
Let $L = \text{Con } (\mathbb{N}, 0, +) \setminus \Delta$ be the lattice of monoid congruences on the naturals, excluding the trivial congruence. As it happens, every $\theta \in L$ is the meet of ...
- 631
1
vote
0
answers
44
views
Lower bound for restricted sumset in ordered groups
Recently in The restricted sumsets in finite abelian groups it is proved that
Suppose that $k \geq 2$ and $A$ is a non-empty subset of a finite abelian
group $G$ with $|G| > 1$. Then the ...
8
votes
1
answer
437
views
Function $\phi$ such that $f(\phi(x,y)) = f(x) + f(y)$
I have a continuous function $f:\mathbb{R}^n\to\mathbb{R}$, and I am looking for a continuous (or at least measurable) function $\phi:\mathbb{R}^{2n}\to\mathbb{R}^n$ such that $f(\phi(x,y))=f(x)+f(y)$....
- 716
2
votes
0
answers
92
views
Geometric interpretation of flags and the role of the rook monoid and Kazhdan–Lusztig theory in $M_n(\mathbb{C})$
Let $G = GL_n(\mathbb{C})$, $B$ be its Borel subgroup, and $P$ a parabolic subgroup. The space $G/B$ corresponds to complete flags in $ \mathbb{C}^n$, and $G/P$ corresponds to partial flags. The ...
- 141
4
votes
1
answer
364
views
Values attained by the coheight of $(H \setminus H^\times)^k$ as a function of $H$ and $k$
Edit (Apr 24, 2017). I'm updating this post in the light of the latest developments of a related thread.
Let $H$ be a multiplicatively written, commutative monoid, and set $M := H \setminus H^\times$,...
CommunityBot
- 1
0
votes
0
answers
61
views
Defining rank of an abelian subgroup using the second centralizer
I recently posted this on MSE, but didn't receive any feedback; so I'm posting it on MO.
I recently came across this article which explored the maximal abelian subgroups of the symmetric group $S_n$. ...
- 63.9k
2
votes
1
answer
188
views
Uniqueness of differences of roots of polynomials over finite field
Let $f$ be a polynomial over a finite field $\mathbf{F}_p$ with $p \neq 2$. Let $R$ be the roots of $f$ in some extension field. I am interested in the multiset of differences $R - R = \{ r - s \mid r,...
- 704
1
vote
1
answer
324
views
Want to show that this sum vanishes modulo p
Let $p\ge 5$ be a prime number, and consider the following sum:
\begin{align}
S &= \sum_{v_0 = 1}^{p - 2} \binom{p - 2}{v_0} \, \theta^{v_0 - 1}(Y) \cdot \theta^{p - 2 - v_0}(Y) \\
&+ \frac{1}{...
- 18.4k
4
votes
1
answer
239
views
True or false? Every left or right cancellative, duo semigroup is cancellative
A semigroup $S$ is duo if $aS = Sa$ for all $a \in S$, where $aS := \{ax: x \in S\}$ and similarly for $Sa$; for instance, every commutative semigroup is duo, and so is every group. On the other hand, ...
- 10.5k
2
votes
1
answer
404
views
Reference request: a cousin to the log semiring
Let $f$ be strictly increasing on $\mathbb{R}$. Then $x \oplus y := f^{-1}(f(x)+f(y))$ gives rise to a strict symmetric monoidal ($\Rightarrow$ commutative monoid) structure on $(\mathbb{R},\ge)$ with ...
CommunityBot
- 1
2
votes
1
answer
287
views
Double estimates relating Ruzsa distance and doubling constant
I am trying to solve the following exercise (2.3.16) from Tao-Vu book.
Let $A,B$ be additive sets with common ambient group $Z$. Show that
$\sigma[A\cup B]\leq e^{d(A,B)}+2e^{4d(A,B)}$. In the ...
CommunityBot
- 1
7
votes
2
answers
331
views
Does every subset of $\mathbb N$ with full natural density contain arbitrarily long geometric progressions?
We use the standard definition of natural density. We say a subset of $\mathbb N$ has full natural density if it has natural density $1$.
Question: Does every subset of the naturals with full natural ...
- 7,013
2
votes
0
answers
89
views
Unique representation as sum of an element of A and a square
Is there a set $A\subseteq\mathbb{Z}$ and a function $f:A\to\mathbb{N}$ such that every integer can be uniquely represented as $a+n^2$ for some $a\in A$ and some $n\geq f(a)$? (Here and in the ...
- 545
7
votes
2
answers
604
views
Density version of the Erdős-Graham conjecture
In 2003 E. S. Croot [Ann. of Math. 157(2)(2003), 545-556] proved the Erdős-Graham Conjecture which states that if $\{2,3,\ldots\}$ is partitioned into finitely many subsets then one of the subsets ...
- 105k
1
vote
0
answers
108
views
Asymptotics for sums of two sets of positive integers
Assume that $A$ and $B$ are subsets of $\mathbb N$, with counting functions verifying $A(x)\gg x^\alpha$ and $B(x)\gg x^\beta$, with $\alpha+\beta<1$. Let $C=A+B$ and $C(x)$ its counting function.
...
- 3,319
5
votes
0
answers
185
views
Gaps in sumsets and difference sets
a) Let $S\subset \{1,2,\dotsc,N\}$ be a fairly thick set (with at least $N^{1-\epsilon}$ elements, say). Suppose that the intersection of, say,
$$3 S - 3 S = \{a_1+a_2+a_3-(a_4+a_5+a_6): a_1,\dotsc,...
CommunityBot
- 1
6
votes
3
answers
551
views
Conjecture about commutative semigroups
Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, ...
- 38.6k
0
votes
0
answers
374
views
Is the Conjecture of Representing Integers as Differences of Semiprimes and Primes Extendable to Products of Distinct Primes?
Conjecture:
Let $k$ and $l$ be fixed distinct positive integers ($k≠l$). Then, for every positive integer $n$, there exist prime numbers $p_1,p_2,…,p_k∈\mathbb{P}$ and $q_1,q_2,…,q_l∈\mathbb{P}$ such ...
- 17
8
votes
1
answer
322
views
Does every cancellative duo semigroup embed into a group?
Prompted by the comments to a recent answer by YCor to a related question (here), I'd like to ask the following:
Q. Does every cancellative duo semigroup embed into a group?
A (multiplicatively ...
- 10.5k
7
votes
2
answers
488
views
Is every cancellative semigroup a subdirect product of subdirectly irreducible cancellative semigroups?
By a classical result of Birkhoff (that is, Theorem 2 in [G. Birkhoff, Subdirect unions in universal algebra, Bull. AMS, 1944]) and the trivial fact that the class of semigroups is closed under the ...
- 10.5k
8
votes
2
answers
596
views
If a semigroup embeds into a group, then is it a subdirect product of groups?
The title has it all:
Q. If a semigroup $S$ embeds into a group, then is $S$ (isomorphic to) a subdirect product of groups?
If yes, then $S$ is a subdirect product of subdirectly irreducible groups,...
- 38.6k
3
votes
0
answers
250
views
Action (of a graded monoid) required
Reference request: Did the construction below appear anywhere before? Any mentions of it or especially any links to something commonly known would be really helpful. I feel that it might be related to ...
- 321
0
votes
0
answers
87
views
Asymptotic behavior of sumsets of squares with restricted congruence conditions
Recall that if $A$ and $B$ are both subsets of the integers, then $A+B=\{a+b:a \in A,b \in B\}$.
Lagrange's four-square theorem states that if $A$ is the set of squares, then $4A=A+A+A+A=\mathbb{N}$.
...
- 101
1
vote
1
answer
453
views
Dimension of a kernel of a linear map
Let $\mathbb{F}$ be a field of characteristic $2$, $n$ be a positive integer and $f_n:\bigoplus\limits_{i=1}^n\mathbb{F}\sigma_{i}\mapsto \bigoplus\limits_{i,j=1,i<j}^n\mathbb{F}\sigma_{i,j}$ be a ...
- 306
0
votes
0
answers
70
views
$\ell^2 \rightarrow L^p ([0,1]^d) $ estimates for trigonometric polynomials
My question concerns $L^p ([0,1]^d)$ estimates for trigonometric polynomials, where both the coefficients and frequencies are coming from general (i.e. not necessarily geometrically special/structured)...
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 ...
- 3,499
3
votes
0
answers
89
views
Ordering the elements of a semigroup by $a \le b$ iff $a=b$ or $b=ab=ba$
Let $S$ be a semigroup, written multiplicatively. The binary relation $\le$ on (the underlying set of) $S$, whose graph consists of all pairs $(a,b) \in S \times S$ such that $a = b$ or $b = ab = ba$, ...
- 10.5k
0
votes
1
answer
128
views
Other, easier, approaches to proving: for $k$ coprime integers summing to zero, there is no bound on $\min\{\Omega(a_1),\ldots,\Omega(a_k)\}$
I put this on Stackexchange, and the question was closed without them specifying why (they just said "no context", even though I did mention the context). Never mind - I have deleted the ...
- 1,819
3
votes
1
answer
168
views
Maximal zero-sum free sequences of $C_3^n$
I am working on the Davenport constant for groups, $D(G)$, which is the minimal number $d$ such that every sequence or multiset of $d$ elements of the group $G$ always contains some non-empty zero-sum ...
0
votes
0
answers
15
views
Finding the number of $k$ element subsets of $A$ such that the sum of the elements in is congruent to a fixed integer $L$ mod$P$
Let $A$ be a set of $p$ elements where $P$ is an odd prime. We are interested in finding the number of $k$ element subsets of $A$ such that the sum of the elements in the subset is congruent to a ...
4
votes
0
answers
148
views
Isomorphism between the reduced C*-algebra of a groupoid and the crossed product of inverse semigroups
In Paterson's book "Groupoids, Inverse Semigroups and their Operator Algebras" he proves that for any r-discrete groupoid $G$ with unit space $G^0$, its full $C^* $-algebra $C^* (G)$ is ...
CommunityBot
- 1
0
votes
0
answers
114
views
Clarifications sought on the paper on the semigroup associated with a free polynomial by Ali Abbas and Abdallah Assi
I have three questions regarding the proof of Proposition 4 on page 4 of this paper here. For those interested in addressing these questions, please refer to some definitions in the first two or three ...
- 63.9k
1
vote
0
answers
95
views
Sieve theory obstruction: prime-sparse and nearly full-differenced sets?
Let $D(A) = {|a-b| : a, b \in A}$ denote the difference set of $A \subseteq \mathbb{Z}$. A set $A \subseteq (x/2, x]$ is almost full-differenced if $|D(A)| \geq \frac{x}{2} - \log x$. Let $C_x$ denote ...
CommunityBot
- 1
3
votes
0
answers
161
views
On generators of the multiplicative semigroup $\{r\in\mathbb Q:\ r>1\}$
The set $M=\{r\in\mathbb Q:\ r>1\}$ is a commutative semigroup with respect to the multiplication. For any integers $a>b\ge1$, we clearly have
$$\frac ab=\prod_{n=b}^{a-1}\frac{n+1}n.$$
So the ...
- 15.6k
3
votes
0
answers
92
views
Reference for the monoidal category structure $X \otimes Y = X + Y + X \times Y$ on a distributive category
Given a distributive category $\mathscr C$ (more generally a rig category), we can define a (semicocartesian) monoidal category structure on $\mathscr C$ with tensor product given by $X \otimes Y := X ...
- 10.7k
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
3
votes
0
answers
53
views
On sets spanning all subspaces of a given dimension in vector spaces over finite fields
Let $n$ be a positive integer, let $p$ be a prime, let $\mathbb F_p$ be the field with $p$ elements, and let $V = \mathbb F_p^n$ be the $n$-dimensional vector space over $\mathbb F_p$.
For an integer $...
- 111
9
votes
1
answer
435
views
On the origin of a fundamental theorem of additive number theory
Given $a, b \in \mathbb Z$, set $[\![a,b]\!] := \{x \in \mathbb Z: a \le x \le b\}$. A basic result in additive number theory goes as follows:
If $A$ is a finite subset of $\mathbb N$ with $0 \in A$ ...
- 10.5k
3
votes
2
answers
493
views
Why can we not find exact values for sizes of cap sets for $d>6$?
I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. ...
- 2,370
6
votes
0
answers
632
views
Generating functions in countable commutative monoids
Let $f: \mathbb{N}_0 \rightarrow \mathbb{C}$ be a function. The power series of $f$ can be viewed as the function $\mathscr{P}_f : q \mapsto \sum_{n \in \mathbb{N}_0}^{} f(n)q^n$ where $q \in \mathbb{...
- 405
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 $$\...
CommunityBot
- 1
5
votes
0
answers
191
views
Do most semigroups have a zero?
It is widely believed in finite semigroup theory that asymptotically almost all finite semigroups $S$, up to isomorphism, are 3-nilpotent, i.e., they satisfy $\#\{abc\,:\,a,b,c\in S\} = 1$. My ...
- 151
2
votes
0
answers
62
views
Maximum distance between consecutive terms in sequence with arbitrarily long APs
Good evening. I am writing a paper on complex analysis, and as a corollary (of my work and others'), I believe that I have managed to deduce the following result.
Proposition: Let $n_1 < n_2 \cdots ...
- 121
5
votes
3
answers
851
views
What are some examples of non-commutative $\mathbb{Q}$-monoids and/or $\mathbb{R}$-monoids?
Definition 0. Let $R$ denote a commutative semiring with $0$ and $1$. By an $R$-monoid, I mean a monoid $M$ equipped with an action $R \times M \rightarrow M$ denoted $r,m \mapsto m^r$, satisfying the ...
- 17k