What tools should I use for this problem?

Question

Suppose we have $d$ cylindrical metal bars, with radius $l$, attached orthogonal to a support in random places:

Now we have to attach bars with radius $k$ EVENLY SPACED, with distance $p$ between their centers, in the same support and without any bar being in top of other:

Determine the possible values for $p$. ($k$ is not necessarily greater than $l$.)

(The way that I think the) Problem: Given a increasing finite sequence $\{a_n\}_{n=1}^d$ of $d$ real numbers and positive real numbers $l$ and $k$, find $p$ and $q$ such that the sequence $\{b_n\}_{n=0}^\infty=\{pn+q\}$ has the property: $$(a_i-l,a_i+l)\cap(b_j-k,b_j+k)=\emptyset\quad \forall i,j.$$ That is: we have open intervals around each $a_i$ with size $2l$ and we must find $p$ and $q$ such that the intervals with size $2k$ around numbers of the form $\{pn+q\}$ has no intersection with the first ones.

Question: How should I approach the problem to find ALL nontrivial solutions? (Note that $p>a_d-a_1$ will trivially solve the problem.)

Edit: I was not clear about looking for all nontrivial solutions.

(Edit) What I expect as an answer: A path to the solution to the problem, that is: an expression for $p$ and $q$ depending on the given data. Something like: "You formulate in the manner A, use results B and calculate C. I leave for you the calculations and minor details."

Edit: As user Timothy Chow pointed out, to give a bound on the number $d$ of bars can drastically make a difference on the possibility for such expression. So consider that $d \le 15$.

About the problem: A student of my class on differential equations asked me that problem and said that would be very helpful to have a 'very nice formula' for $p$ and $q$. He is doing university in engineering and already works in a big company here (Brazil). At first it appeared to me to be a 'very simple-trivial-easy' problem because of the finiteness of the first sequence, but the fact that the $a_n$'s are not necessarily evenly spaced make all too hard.

About the post itself: I had no idea of how to ask for help with that problem, so I asked in meta.mathoverflow about it and user @fedja very kindly answered me how to do it. Any help with a better title and appropriate tags will be very welcome.

My attempt to solve the problem: The problem looks like an optimization problem, so I tried to define a function $F(p,q)$ such the solutions correspond to the minimum of this function. One option is: $$F(p,q)=\int_{\mathbb{R}}f(x)g(x)\,dx,$$
where $$f(x) = \begin{cases} 1, & \text{if $x \in (a_i-l,a_i+l)$ } \\ 0, & \text{if $x \notin (a_i-l,a_i+l)$ } \end{cases}$$ and $$g(x) = \begin{cases} 1, & \text{if $x \in (b_i-k,b_i+k)$ } \\ 0, & \text{if $x \notin (b_i-k,b_i+k)$ } \end{cases}.$$ Certainty $F(p,q)\ge0$ $\forall p,q$. Also $F(p,q)=0$ is a solution to the problem. As $f(x)\neq0$ only for a finite number of finite intervals this becomes $$F(p,q)=\sum_{n=0}^d\int_{a_n-l}^{a_n+l}g(x)\,dx.$$ That $g(x)$ can be written as a Heaviside function applied to a cosine function: $$g(x)=H\left(\cos\left(\frac{2\pi}{p}x-\frac{2\pi}{p}q\right)-\cos\left(\frac{2\pi k}{p}\right)\right).$$ So we have $$F(p,q)=\sum_{n=0}^d\int_{a_n-l}^{a_n+l}H\left(\cos\left(\frac{2\pi}{p}x-\frac{2\pi}{p}q\right)-\cos\left(\frac{2\pi k}{p}\right)\right) \, dx.$$

For this integral I tried to use analytic approximations to the step function like the ones in the Wikipedia article, but none of the expressions seems to lead to an integral that can be expressed in closed form.

I still have a feeling that this problem could be solved in closed form. Since I had my master degree (about 10 years ago) I had never again contact to some areas of math like abstract algebra (fields, rings, etc). In all that time I essentially taught Linear Algebra and Differential Equation courses and just started my PhD in Physics, so all my experience is way too limited. I feel like someone with experience in Algebra would say "Oh, that is very simple application of Fermat's little theorem and euclidean division...". Or may be some one with experience in Measure theory "It's a easy calculation with the Lebesgue-Sobolev formula...". Any help will be very welcome!

Answer 1

If $m=k+\ell$, then the question reduces to when the intervals $(a_i-m,a_i+m)\mod p$ do not cover the full interval $[0,p]$. The answer is, of course, a union of finitely many intervals and the interesting question is how many they can be and how to compute them fairly quickly. Note that the interesting range of $p$ is $[2m,2md]$ ($p<2m$ gives just too dense set to avoid a single initial bar and $p>2md$ is long enough to admit $q$ by simple length comparison). It may be convenient to denote $\eta=1/p$ and to ask for which eta the intervals $(\eta a_j-\eta m, \eta a_j+\eta m)\mod 1$ cover or do not cover $[0,1]$.

The first (unfortunate) observation is that the number of constituting intervals in that set can be arbitrarily large even for $d=2$. Indeed, if you think of $a_1=0$ and $a_2=a\gg 1$ with $m=\frac 14$, say, then we have one stationary slowly expanding interval $(-0.25\eta,0.25\eta)$ and the other interval that goes around at the huge speed $a$ and also slowly expands when $\eta$ goes from $1$ to $2$ (the interesting range). That crazy rotation gives us about $a$ switches from covering to not covering, so no "linear in $d$" (or even depending on $d$ alone) computation time is feasible. The number of intervals can certainly be as large as $\frac{a_d-a_1}{m}$.

Fortunately, we can easily describe all possble endpoints of those intervals. They are all of the kind $\frac{a_j-a_i\pm 2m}{n}$ where $i\le j$ and $n$ is a positive integer. To fit into the interval $[2m,2md]$ we must have $n\le\frac{a_j-a_i}m+2$, so we have about $\frac{a_d-a_1}m$ choices of $n$ and about $d^2$ choices of $i,j$. On each interval between these endpoints the answer to the covering question remains the same, so we can just pick a particular value of $p$ for each interval and check what happens with that $p$. This is not hard but still takes $d\log d$ time (sorting the intervals modulo $p$ in the increasing order and going left to right over the resulting partition in the search of an empty spot). Thus, with this naive approach, the running time becomes $$ \frac{a_d-a_1}{m}d^3\log d\,. $$ As I showed, the first factor cannot be avoided, so the only question is whether we can reduce the second (depending of $d$) factor to something smaller.

Answer 2

As noted in the comments, it appears unlikely that a simple closed formula exists, but here is a way to solve the problem numerically.

By rescaling one can choose $a_0=0$ and $a_d=1$. Because the overlap depends only on $k+l$, it is sufficient to consider the case $l=0$. Also the width in the following is denoted as $k$ instead of $2\,k$. One thus has a list $A=(0,a_1,\ldots,1)$ and tries to find a spacing $p<1$ and width $ k>0$ such that a regular lattice with interval width $ k$ does not intersect $A$. For fixed $p$, the possible values of $k$ can be found by sorting the list $\left({\rm mod}(a_i,p)\right)_{i=0,\ldots,d}$ and finding the maximal circular gap $g(p)$. For all values $ k<g(p)$ a non-overlapping periodic lattice with distance $p$ and width $k$ can be found.

To find the possible values of $p$ for given $k$ one has to make use of the fact that $g(p)$ is continuous (piecewise linear) and calculate it on a sufficiently fine grid in the interval $p\in [k,1]$ to see if there is a value of $p$ for which $g(p)>k$. I guess that these calculations can be done quite efficiently, maybe even in time $O(d)$. The Mathematica code below implements the function $g$ and creates the example plot for the list $A=(0,0.123, 0.33, 0.71,1)$ and $k=0.08$. The allowed values of $p$ are therefore the values which are (greater than $k$ and) with $g(p)$ above the orange line.

Gap[x_, p_] := Module[{ll}, ll = Append[Sort[Mod[#, p] & /@ Join[{0}, x, {1}]], p]; Max[ll[[2 ;;]] - ll[[;; -2]]]]

Plot[{Gap[{0.123, 0.33, 0.71}, p], 0.08}, {p, 0, 1}, PlotTheme -> "Detailed", AspectRatio -> 1, FrameLabel -> {"p", "g(p)"}]