16
$\begingroup$

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

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:enter image description here

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!

$\endgroup$
12
  • 2
    $\begingroup$ Thanks for all the work you put into a well crafted post, including the MMO post to make sure it was best possible. $\endgroup$
    – LSpice
    Dec 1, 2021 at 3:13
  • 3
    $\begingroup$ Since you're asking about what tools: I'm not sure I would consider this as a continuous problem at all. How close to rationally ratio'd are your $k$ and $l$ (and the distances $a_i$, I suppose)? I would treat this as a number theory problem. $\endgroup$ Dec 1, 2021 at 3:34
  • 2
    $\begingroup$ That is to say, try and treat all parameters as integral and look for solutions that way, as what you're essentially trying to do is 'miss' a set with arithmetic progressions. Depending on the number of gaps, you may be able to do a discrete search based on which gaps you believe one (or more) bars will go into — that is, consider discrete configurations and determine which ones allow a valid solution. $\endgroup$ Dec 1, 2021 at 3:45
  • 1
    $\begingroup$ @LSpice, I appreciate very much your comment! $\endgroup$ Dec 1, 2021 at 12:54
  • 3
    $\begingroup$ Jeff Erickson has written a two-page article on Finding Longest Arithmetic Progressions. This is not exactly the same as your problem but I think it's close. In particular, I suspect that dynamic programming will be a good approach to your problem. (But my intuition is that a "closed form" is too much to hope for.) $\endgroup$ Dec 1, 2021 at 14:10

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

enter image description here

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)"}]

$\endgroup$
4
  • 1
    $\begingroup$ I would write Gap[x_, p_] := Join[Mod[x, p], {0, Mod[1, p], p}] // Sort // Differences // Max $\endgroup$
    – Matt F.
    Dec 5, 2021 at 22:13
  • $\begingroup$ @MattF.: That is neater. I didn't know "Differences" worked around that for ages ... $\endgroup$ Dec 5, 2021 at 23:47
  • $\begingroup$ @KarlFabian, first: thank you! Second: where are you considering the sequence to start? Because the $q$ makes a huge difference (I found by experimenting that for different $q$ we get different $p$), and I cannot understand where it enters. Third: I google "maximal circular gap " and find no results for this definition. What exactly it is? $\endgroup$ Dec 7, 2021 at 15:53
  • 1
    $\begingroup$ @Diego Santos: For fixed $p$ you can consider the numbers $\left({\rm mod}(a_i,p)\right)_{i=0,\ldots,d}$ to lie on a circle of circumference $p$. We are interested in the largest gap between these numbers. In principle this can occur between the largest number $\leq p$ and the smallest number $\geq 0$, which here is always $a_0=0$. Therefore one has to add also $p$ itself to the list from which the maximal gap is determined. A possible value of $q$ is then any point in a gap that is larger then $k$, which is more than $k/2$ away from both neighbors. $\endgroup$ Dec 7, 2021 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.