5
$\begingroup$

This is a naive question and I'm afraid it might be better placed on math.se. I would like to leave it to your judgement.

I would like to know what is known about sets $A$ of natural numbers such that $A$ contains $0$ and there exists a natural number $n$ such that the sum of $n$ $A$s is a submonoid of $\Bbb N$ or

$$\underbrace{A+A+\ldots+A}_{n\text{ times}}=\langle A\rangle,$$

where $\langle A\rangle$ is the semigroup generated by $A.$ Or yet in other words, sets, not necessarily containing $0$, such that it is enough to take sums of their elements of bounded length to already obtain a semigroup.

I would prefer not to embarrass myself by trying to say anything about these sets. I'll just ask what known sufficient and necessary conditions for a set to be such there are. And also, is there a name for such sets?

Improve this question
$\endgroup$
3
  • $\begingroup$ Fix $n$ and try to see which $A$ work for this $n$. For example, for $n=3$, the set $A=\{0,1,4,7,10,...,3k+1,...\}$ easily works, but so also does the set $A=\{0,1,3,7,12,18,..\}$ even though for the latter the gaps between consecutive numbers become bigger and bigger (and even though I don't know what is the common term). We could have used $23$ instead of $18$, but making bigger gaps early may necessitate making smaller gaps later. I am pretty sure that for $n=3$ the set of triangular numbers $A=\{0,1,3,6,10,15,21,..,\dfrac{n(n+1)}2,..\}$ works(?) providing example where the gaps get larger. $\endgroup$
    – Mirko
    Commented Apr 16, 2015 at 6:19
  • $\begingroup$ my comment above assumes that $\langle A\rangle=\mathbb N$. I may not understand what is "the semigroup generated by $A$". If $A$ contains all positive multiples of $3$, and all multiples of $5$ starting with $15$, is then $\langle A\rangle = \{3,6,9,12,15,18,20,21,23,24,25,...\}$ thus containing all positive integers beyond $23$ (yet not containing $1,2,4,5,7,8,10,11,13,14,16,17,19,22$)? Does it have to contain $0$? I guess $A$ itself (and hence $\langle A\rangle$ too) should contain $0$ (since you require it explicitly). $\endgroup$
    – Mirko
    Commented Apr 16, 2015 at 7:31
  • $\begingroup$ @Mirko I think it's simpler to think about the case of sets containing zero only. $\endgroup$
    – Michał Masny
    Commented Apr 17, 2015 at 19:28

1 Answer 1

Reset to default
6
$\begingroup$

This question is a special case of a problem proposed by John Brzozowski in 1966 during the seventh SWAT (now FOCS) Conference. Let $A$ be a finite alphabet and let $A^*$ be the free monoid on $A$. A subset $L$ of $A^*$ has the finite power property if there exists a natural number $n$ for which $L^* = L^n$. Brzozowski's original question was the following:

Given a regular subset $L$ of $A^*$, decide whether or not $L$ has the finite power property.

After some preliminary remarks by Linna [4], the problem was shown to be decidable independently by K. Hashiguchi [1] and Imre Simon [5]. It was also shown to be undecidable for context-free languages [2]. An elegant purely semigroup theoretic proof was given by Kirsten [3].

Hashiguchi's solution is very short and works directly on the automaton recognizing $L$. Imre Simon reduced the finite power property to the finite closure problem for the tropical semiring. (Recall that the adjective tropical was coined in honor of Imre Simon).

The case you consider is $A = \{a\}$, a much simpler case and deciding the finite power property for regular subsets of $\mathbb{N}$ (= finite unions of arithmetic progressions) is likely to be much easier. Context-free and regular subsets coincide in $\mathbb{N}$, but perhaps the problem is still decidable for larger classes.

[1] K. Hashiguchi, A decision procedure for the order of regular events, Theoret. Comput. Sci. 8 (1979) 69–72.

[2] C. B. Hughes and S. M. Selkow. The finite power property for context- free languages. Theoretical Comput. Sci., 15:111-114, 1981.

[3] D. Kirsten, The finite power problem revisited, Information Processing Letters 84 (2002) 291–294

[4] M. Linna, Finite power property of regular languages, in “Automata, Languages and Programming” (M. Nivat, Ed.), pp. 87-98, North-Holland, Amsterdam, 1973.

[5] I. Simon, Limited subsets of a free monoid, in: Proceedings of the 19th IEEE Annual Symposium on Foundations of Computer Science, North Carolina Press, 1978, pp. 143–150.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Regular subsets of N are the union of a finite set with an arithmetic progression. Can anything be said about other sets? $\endgroup$
    – Benjamin Steinberg
    Commented Apr 16, 2015 at 17:44
  • $\begingroup$ Thank you for your answer. It is not a full answer to my question, as Benjamin mentions, but the question has quite a lot of views and there aren't any comments that would give hope for a fuller one. I think I'll accept it then. $\endgroup$
    – Michał Masny
    Commented Apr 23, 2015 at 0:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .