Technical Report CS-2005-02

TR#:CS-2005-02
Class:CS
Title: On Smooth Sets of Integers
Authors: Ami Litman, Shiri Moran-Schein
PDFCS-2005-02.pdf
Abstract: This work studies evenly distributed sets of integers --- sets whose quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation. Namely, for $\rho,\Delta\in\reals$ a set $A$ of integers is {\em $(\rho,\Delta)$-smooth} if $\mbox{abs}(\card{I}\cdot \rho-\card{I\cap A})<\Delta$ for any interval $I$ of integers; a set $A$ is $\Delta$-smooth if it is $(\rho,\Delta)$-smooth for some real number $\rho$. The paper introduces the concept of $\Delta$-smooth sets and studies their mathematical structure. It focuses on tools for constructing smooth sets having certain desirable properties and, in particular, on mathematical operations on these sets. Two additional papers of us build on the work of this paper and present practical applications of smooth sets to common and well studied scheduling problems. One of those mathematical operations is composition of sets. For two infinite sets $A,B\subseteq \naturals$, the {\em composition} of $A$ and $B$ is the subset $D$ of $A$ such that, for all $i$, the $i$-th member of $A$ is in $D$ iff the $i$-th member of $\naturals$ is in $B$. This operator enables the partition of a $(\rho,\Delta)$-smooth set into two sets that are $(\rho_1,\Delta)$-smooth and $(\rho_2,\Delta)$-smooth, for any $\rho_1,\rho_2$ and $\Delta$ obeying some reasonable restrictions. Another powerful tool for constructing smooth sets is a partial one-to-one function $f$ from the unit interval into the natural numbers having the property that any real interval $X\subseteq [0,1)$ has a subinterval $Y$ which is `very close' to $X$ s.t.\ $f(Y)$ is $(\rho,\Delta)$-smooth, where $\rho$ is the length of $Y$ and $\Delta$ is a small constant.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2005/CS/CS-2005-02), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2005
To the main CS technical reports page

Computer science department, Technion
admin