## Return to Question

2 added 147 characters in body

Given real numbers $a$ and $b$, and an integer $n \geq 2$, let $f(n,a,b)$ be the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) minus the maximum of $(nint(ja+b)-nint(ia+b)-1)/(j-i)$ (for $1 \leq i < j \leq n$), where $nint$ is the nearest integer function. What is known about the rate at which $f(n,a,b)$ goes to 0 as $n$ goes to infinity, for "generic" real numbers $a, b$? (That is, real numbers whose continued fractions have convergents that grow as dictated by Khinchin's law.) Experiments suggest that $f(n,a,b) = O(1/n^2)$.

This is related to the question of how accurately one can infer the slope of a line from a digitized version of the line; if there is any literature on this question, I would be very interested in pointers.

I am also interested in knowing how one can most efficiently compute the minimum of $f(n,a,b)$.(nint(ja+b)-nint(ia+b)+1)/(j-i)$(for$1 \leq i < j \leq n$) and the maximum of$(nint(ja+b)-nint(ia+b)-1)/(j-i)$(for$1 \leq i < j \leq n\$).

For context, I'll mention that several recent postings of mine (especially http://mathoverflow.net/questions/54731/sums-of-fractional-parts-of-linear-functions-of-n) approach this question from another angle. Specifically, my posting from last week is related to an estimator of the slope of the line that can be computed in linear (as opposed to quadratic) time but has typical error $O(1/n^{3/2})$.

1

# inferring the slope of a digitized line

Given real numbers $a$ and $b$, and an integer $n \geq 2$, let $f(n,a,b)$ be the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) minus the maximum of $(nint(ja+b)-nint(ia+b)-1)/(j-i)$ (for $1 \leq i < j \leq n$), where $nint$ is the nearest integer function. What is known about the rate at which $f(n,a,b)$ goes to 0 as $n$ goes to infinity, for "generic" real numbers $a, b$? (That is, real numbers whose continued fractions have convergents that grow as dictated by Khinchin's law.) Experiments suggest that $f(n,a,b) = O(1/n^2)$.

This is related to the question of how accurately one can infer the slope of a line from a digitized version of the line; if there is any literature on this question, I would be very interested in pointers.

I am also interested in knowing how one can most efficiently compute $f(n,a,b)$.

For context, I'll mention that several recent postings of mine (especially http://mathoverflow.net/questions/54731/sums-of-fractional-parts-of-linear-functions-of-n) approach this question from another angle. Specifically, my posting from last week is related to an estimator of the slope of the line that can be computed in linear (as opposed to quadratic) time but has typical error $O(1/n^{3/2})$.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 33, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9396283626556396, "perplexity_flag": "head"}