0
$\begingroup$

Say we have an arithmetic progression in $Z_n$ like $3, 6, 9, 12, ...$ etc. If you move a sliding window of at least 3 values over the progression the 'density' in that subset compared to if the window 'had no holes', is always the same, $\frac{1}{3}$ (I think the term I'm looking for is Natural Density, but this is a new concept for me so I'm not sure if I'm using it 100% correctly).

Arithmetic progressions also have the nice property that they can be described with a fixed amount of space, e.g. for an arithmetic progression you only need to know the starting number and the constant difference to derive the rest of the numbers in the progression.

What types of monotonically increasing progressions can be described with fixed space are known that have "varying" density? By "fixed space" I mean to avoid a hard coded list, instead focusing on sequences that can be generated from some finite set of starting numbers. By "varying" I mean:

  1. A sliding window over the values should not see the same density every time, and that the density seen should increase and decrease, so the density should not be strictly monotonically increasing/decreasing, even though the progression is. So for example a sequence of triangular numbers would not work, because they only ever become further apart.
  2. I should be able to choose a window size vastly greater than the amount of space used to describe the progression and still have it vary (so no cycling through a fixed list of differences).

Apologies if I have not formalized this enough :) I think I'm stumbling on something that must be studied already but I don't know the terminology.

Edit: I was trying to keep things succinct but more constraints are needed. My ultimate goal is to use these sequences on a computer, so sequences that are more easily computable have preference. I'd also like to be able to easily compute the Nth element, without calculating every prior element.

  • 0
    @MarioCarneiro: I've added a constraint that I think gets at what I'm going for, getting the Nth element easily. I don't totally follow your explanation for why a set of fixed bits doesn't work -- are you saying that my specific example of constraining that the 3rd/5th/7th bit wouldn't work, or are you just saying it's not always true that any subset of fixed bits will work because if you only pick a chunk of adjacent digits at the beginning/end you only get multiples or all numbers below a threshold?2012-12-16

1 Answers 1

1

If you put any constraint on any set of fixed bits (as in fixed with respect to the radix point), the constraint can be converted to the form "the least-significant $m$ digits form a number in this list...". Let me back up this claim with a proof. Say the constraint is $P(n):=[n_{x_1}=b_1\wedge n_{x_2}=b_2\wedge\dots\wedge n_{x_k}=b_k]$, where $n_i$ is the $i$-th least-significant bit, the $\{x_i\}_1^k$ form an increasing sequence, and $b_i\in\{0,1\}$ are fixed constants for each $i$.

Then the most-significant constraint is for the $x_k$-th bit, so letting $m=x_k+1$, if I let $A=\{n\in\{0,1,\dots,2^m-1\}:P(n)\}$, then if there is some $n\in A$, adding $2^m$ to $n$ will not change any bits below the $m$-th position, so $P(n+2^m)$ is also true, and indeed $P(n+2^ma)$ is true for $a\in\mathbb Z$ as well. Moreover, the same is true for numbers that do not satisfy the constraint, so that $P(n+2^ma)\iff P(n)$ for all $a\in\mathbb Z$. Therefore, $P(n)\iff n\bmod2^m\in A.$

Thus if the window is of size $2^m$, the mapping $n\mapsto n\bmod2^m$ takes any set $\{c,\dots,c+2^m-1\}$ to $\{0,\dots,2^m-1\}$, so the "window density" is $|A|/2^m$ regardless of $c$. You get this same result if the window size is a multiple of $2^m$, so it fails your "cycling through a fixed set of differences" test.

  • 0
    Yes, much. Thanks for your patience explaining :)2012-12-16