Search

1. Motivation. Many variants of the notion of automaton have appeared in the literature. We find it convenient here to adopt the notion of E. F. Moore [7]. Inasmuch as Rabin-Scott [9] adopt this notion, too, it is convenient to refer to [9] for various results presumed here. In particular, Kleene's theorem [5, Theorems 3, 5] is used in the form in which it appears in [9]. It is often perspicacious to view regular expressions, and this notion is used in the sense of [3]. In general, we are concerned with the problems of automatically designing an automaton from a specification of a relation which is to hold between the automaton's input sequences and determined output sequences. These "design requirements" are given via a formula of some kind. The problems with which we are concerned have been described in [1]. With respect to particular formalisms for expressing "design requirements" as well as the notion of automaton itself, the problems are briefly and informally these: (1) to produce an algorithm which when it operates on an automaton and a design requirement produces the correct answer to the question "Does this automaton satisfy this design requirement?", or else show no such algorithm exists; (2) to produce an algorithm which operates on a design requirement and produces the correct answer to the question "Does there exist an automaton which satisfies this design requirement?", or else show no such algorithm exists; (3) to produce an algorithm which operates on a design requirement and terminates with an automaton which satisfies the requirement when one exists and otherwise fails to terminate, or else show no such algorithm exists. Interrelationships among problems (1), (2), (3) will appear in the paper [1]. This paper will also indicate the close connection between problem (1) and decision problems for truth of sentences of certain arithmetics. The paper [1 ] will also make use of certain results concerning weak arithmetics already obtained in the literature to obtain answers to problems (1) and (3). Thus

Let A = { a s + n s Z } s = 1 k A= \{a_{s}+n_{s}\mathbb {Z}\}^{k}_{s=1} ( n 1 ⩽ ⋯ ⩽ n k ) n_{1} \leqslant \cdots \leqslant n_{k}) be a system of arithmetic sequences where a 1 , ⋯ , a k ∈ Z a_{1}, \cdots ,a_{k}\in \mathbb {Z} and n 1 , ⋯ , n k ∈ Z + n_{1},\cdots ,n_{k}\in \mathbb {Z}^{+} . For m ∈ Z + m\in \mathbb {Z}^{+} system A A will be called an (exact) m m -cover of Z \mathbb {Z} if every integer is covered by A A at least (exactly) m m times. In this paper we reveal further connections between the common differences in an (exact) m m -cover of Z \mathbb {Z} and Egyptian fractions. Here are some typical results for those m m -covers A A of Z \mathbb {Z} : (a) For any m 1 , ⋯ , m k ∈ Z + m_{1},\cdots ,m_{k}\in \mathbb {Z}^{+} there are at least m m positive integers in the form Σ s ∈ I m s / n s \Sigma _{s\in I} m_{s}/n_{s} where I ⊆ { 1 , ⋯ , k } I \subseteq \{1,\cdots ,k\} . (b) When n k − l > n k − l + 1 = ⋯ = n k n_{k-l}>n_{k-l+1}= \cdots =n_{k} ( 0 > l > k ) 0>l>k) , either l ⩾ n k / n k − l l \geqslant n_{k}/n_{k-l} or Σ s = 1 k − l 1 / n s ⩾ m \Sigma ^{k-l}_{s=1}1/n_{s} \geqslant m , and for each positive integer λ > n k / n k − l \lambda >n_{k}/n_{k-l} the binomial coefficient ( l λ ) \binom l{ \lambda } can be written as the sum of some denominators > 1 >1 of the rationals Σ s ∈ I 1 / n s − λ / n k , I ⊆ { 1 , ⋯ , k } \Sigma _{s\in I}1/n_{s}- \lambda /n_{k}, I \subseteq \{1,\cdots ,k\} if A A forms an exact m m -cover of Z \mathbb {Z} . (c) If { a s + n s Z } s = 1 s ≠ t k \{a_{s}+n_{s}\mathbb {Z}\}^{k}_{\substack {s=1\ s\not =t}} is not an m m -cover of Z \mathbb {Z} , then Σ s ∈ I 1 / n s , I ⊆ { 1 , ⋯ , k } ∖ { t } \Sigma _{s\in I}1/n_{s}, I \subseteq \{1,\cdots ,k\}\setminus \{t\} have at least n t n_{t} distinct fractional parts and for each r = 0 , 1 , ⋯ , n t − 1 r=0,1,\cdots ,n_{t}-1 there exist I 1 , I 2 ⊆ { 1 , ⋯ , k } ∖ { t } I_{1},I_{2} \subseteq \{1,\cdots ,k\}\setminus \{t\} such that r / n t ≡ Σ s ∈ I 1 1 / n s − Σ s ∈ I 2 1 / n s r/n_{t} \equiv \Sigma _{s\in I_{1}}1/n_{s}-\Sigma _{s\in I_{2}}1/n_{s} (mod 1). If A A forms an exact m m -cover of Z \mathbb {Z} with m = 1 m=1 or n 1 > ⋯ > n k − l > n k − l + 1 = ⋯ = n k n_{1}> \cdots >n_{k-l}>n_{k-l+1}= \cdots =n_{k} ( l > 0 l>0 ) then for every t = 1 , ⋯ , k t=1, \cdots ,k and r = 0 , 1 , ⋯ , n t − 1 r=0,1,\cdots ,n_{t}-1 there is an I ⊆ { 1 , ⋯ , k } I \subseteq \{1,\cdots ,k\} such that Σ s ∈ I 1 / n s ≡ r / n t \Sigma _{s\in I}1/n_{s} \equiv r/n_{t} (mod 1).