I. Counting Arithmetic Progressions
Given an arbitrary increasing sequence of positive integers $S$ there is associated with it, a counting function $\alpha_S(n)$ which determines the number of arithmetic progressions[1] up to $s_n \in S$. The counting function for the positive integers, and consequently all infinite arithmetic progressions, is given by the formula listed under A330285 (OEIS)[2]:
\[ \sum_{k=1}^n \sum_{j=1}^k \Big{\lfloor} \frac{k-1}{j+1} \Big{\rfloor} \ . \]
We may further generalize from this "AP" counting function, $\alpha_{\mathbb{Z}^+}(n)$, all other functions which count progressions over integer sequences via the equation
\[ \alpha_S(n) = \sum_{k=1}^n \alpha_{\mathbb{Z}^+}(k) \pi (n,k) \]
where $\pi (n,k)$ is the number of primitive arithmetic progressions of length $k$, up to the $n$-th element of $S$ .
A primitive progression is any subset
\[ \{ s, s+d, \ ... \ , s+(k-1)d \} \subset \{ s_1, s_2, \ ... \ , s_n \} \]
such that \[ \{ s-d, s+kd \} \cap \{s_1, s_2, \ ... \ , s_n \} = \emptyset \]
and
\[ \{s, s+d, \ ... \ , s+(k-1)d \} \not\subset \{s', s'+d', \ ... \ , s'+(j-1)d' \} \]
for $k-1 \leq j$, $d' < d$.
II. Relative Arithmetic Density
There are two other uses for our counting function over the positive integers which will be discussed in both this section as well as the following section. The first application involves computing the relative arithmetic density of our sequence $S$, but before we begin it is necessary to elaborate on the definition of partial densities.
Let us consider the fact that the number of progressions up to $s_n$ is merely a fraction of all subsequences over the given interval. The partial density $D_S(n)$ therefore is equal to
\[ \frac{\alpha_S(n)}{2^n - T_n - 1} \]
where $T_n$ is the $n$-th triangular number and the denominator counts subsequences of length three or greater. The infinite sum of partial densities over $\mathbb{Z}^+$ is approximately $2.8956356243$, and will be referred to as Layman's constant[3]. The exact value of the infinite series of partial densities requires further analysis, in the meantime we can still use Layman's constant to construct a definition for relative densities in general by comparing arbitrary number sequences with the positive integers themselves. The relative arithmetic density $\mathcal{D}(S)$ can thus be defined
\[ \frac{\sum_{n=1}^\infty D_S(n)}{\sum_{n=1}^\infty D_{\mathbb{Z}^+}(n)} \]
which is always some positive value less than or equal to one.
III. Natural Arithmetic Density
The second use for our AP counting functions involves a more naturalistic interpretation of arithmetic density, as far as real number valuations are concerned. We can arrive at such a definition by taking advantage of the fact that the counting function for any infinite progression has maximal growth. It then becomes an arbitrary choice of which complementary sequence we might use to construct a suitable infinite series for our valuation.
The author has chosen the sequence of factorials because firstly they converge for all AP counting functions, and secondly because they allow for more convenient algebraic analysis. The formula for the natural arithmetic density of $S$ is thus defined
\[ \delta(S) = \sum_{n=1}^\infty \frac{\alpha_S(n)}{(n-1)!} \ . \]
This series is approximately $1.4263891989$ when the counting function is taken over any infinite progression. For the rare case when there is only one progression of length three at the beginning of the given sequence, the series above is equal to $e-2$.
IV. The Partitional Convergence Theorem
(i) Proof of the theorem.
Assuming the infinite series
\[ \sum_{n=1}^\infty \frac{1}{s_n} = \infty \ , \]
then there exists some subsequence $\{ s_1', s_2', \ ... \ \}$ for which
\[ \sum_{k=n_1}^{n_1} \frac{1}{s_k} < \sum_{k=n_1+1}^{n_2} \frac{1}{s_k} < \sum_{k=n_2+1}^{n_3} \frac{1}{s_k} < \ ... \] and
\[ \sum_{k=n_1}^{n_1} \frac{1}{s_k} > \sum_{k=n_1+1}^{n_2-1} \frac{1}{s_k} > \sum_{k=n_2+1}^{n_3-1} \frac{1}{s_k} > \ ... \ , \]
where $n_1=1$, $s_m'=s_{n_m}$. We can deduce that this sequence of finite series must be constructable, otherwise the infinite sum of reciprocals would not diverge. What is not immediately evident, however, is that each of these finite series should converge to the same value from below. We denote this divergence constant as $C$, and we will further expand on its significance in the following subsection.
In order to establish our proof, let us first draw our attention to the terminal values at the end of each finite series. Without the addition of these single terms, any particular series falls short of those before it according to the second inequality above. Therefore, if all of the finite series are to diverge from any particular constant, that would imply each terminal value is greater than the previous one, or $\frac{1}{s_m'} < \frac{1}{s_{m+1}'}$. This cannot be the case since our infinite subsequence is monotonically increasing, and so its reciprocal elements must tend toward zero. As an example of the proof, let it be noted that the divergence constant for the harmonic series is $\log(3)$.
Before leaving the present topic, there are two other constants which should be briefly discussed for future reference. These are the criticality constant $\kappa$, and the co-criticality constant $\bar{\kappa}$. We can calculate them using the two infinite series
\[ \sum_{m=1}^\infty \frac{1}{n_m} \] and
\[ \sum_{m=1}^\infty \frac{1}{s_m'} \ , \]
respectively. In the case when $S= \mathbb{Z}^+$ these two constants are equal, and their value is
\[ \sum_{m=1}^\infty \frac{2}{3^m-1} = 2 \Bigg( \frac{\log(\tfrac{3}{2}) - \Psi_{\frac{1}{3}}(1)}{\log(3)} \Bigg) \]
\[ \sum_{m=1}^\infty \frac{2}{3^m-1} = 2 \Bigg( \frac{\log(\tfrac{3}{2}) - \Psi_{\frac{1}{3}}(1)}{\log(3)} \Bigg) \]
where $\Psi_q(x)$ is the $q$-digamma function[4].
(ii) Alternative representation of divergent series.
A further consequence of the theorem is that partial sums of divergent series can now be represented using the divergence constant mentioned above. To do so requires the introduction of an error function which adjusts the constant according to the interval over which the function is taken, i.e.
\[ \sum_{k=n_{m-1}+1}^{n_m} \frac{1}{s_k} = C - \text{Err}(m) \ . \]
According to this definition, it follows that the partial sum up to $s_m'$ is given by the formula
\[ \sum_{k=1}^{n_m} \frac{1}{s_k} = Cm - \sum_{k=1}^m \text{Err}(k) \ . \]
We can then expand upon this equation by introducing balancing coefficients $\beta_{m,k}$, such that $n_{m-1}+1 \leq k \leq n_m$, which allow us to compute partial sums over the $m$-th interval $\{ s_{n_{m-1}+1}, s_{n_{m-1}+2}, \ ... \ , s_{n_m} \}$. These are implemented in the following manner
\[ C \beta_{m,k} - \text{Err}(m) = \sum_{j=n_{m-1}+1}^k \frac{1}{s_j} \] which implies
\[ C \sum_{j=1}^{\nabla n_m-1} \beta_{m,j} - (\nabla n_m - 1) \text{Err}(m) = \sum_{k=n_{m-1}+1}^{n_m} \sum_{j=1}^{\nabla n_m-1} \frac{\nabla n_m - j}{s_k} \]
where $\nabla$ is the backward difference operator[5].
REFERENCES
[1] Weisstein, Eric W. "Arithmetic Progression." From Mathworld--A Wolfram web resource. (https://mathworld.wolfram.com/ArithmeticProgression.html)
[2] "A330285." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A330285)
[3] "A051336." The On-Line Encyclopedia of Integer Sequences. (https://oeis.org/A051336)
[4] Weisstein, Eric W. "q-Polygamma Function." From Mathworld--A Wolfram web resource. (https://mathworld.wolfram.com/q-PolygammaFunction.html)
[5] Weisstein, Eric W. "Backward Difference." From Mathworld--A Wolfram web resource. (https://mathworld.wolfram.com/BackwardDifference.html)
No comments:
Post a Comment