Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently encountered the following equality ($\{\}$ denotes fractional part):

$$\sum_{k=1}^{65}k\left\{\frac{8k}{65}\right\}=\sum_{k=1}^{65}k\left\{\frac{18k}{65}\right\}$$

and found it very interesting as most of the individual summands on one side of the equation do not have a corresponding match on the other side. Investigating further, I found several other similar equalities:

$$\sum_{k=1}^{77}k\left\{\frac{9k}{77}\right\}=\sum_{k=1}^{77}k\left\{\frac{16k}{77}\right\}$$

$$\sum_{k=1}^{77}k\left\{\frac{17k}{77}\right\}=\sum_{k=1}^{77}k\left\{\frac{24k}{77}\right\}$$

$$\sum_{k=1}^{85}k\left\{\frac{7k}{85}\right\}=\sum_{k=1}^{85}k\left\{\frac{22k}{85}\right\}$$

Does anyone have any idea what general principle/pattern these arise from?

share|improve this question
    
It may help to rewrite it like this: $\sum_{k=1}^{n}k\{\frac{ak}{n}\} = \sum_{k=1}^{n}k\frac{ak \mod n}{n}$ –  Michael Stocker Jul 21 at 12:37
    
@MichaelStocker And then you can remove the division, since it just scales the values... –  Thomas Andrews Jul 21 at 12:40
    
What does it look like when you write it in terms of Dedekind sums? –  Gerry Myerson Jul 21 at 13:05
    
It's interesting that, in the examples I've run (still relatively small) there are always $1,2,$ or $4$ numerators that yield the same value, but never $3$ or more than $4$. I've only been checking denominators that are a product of two primes. –  Thomas Andrews Jul 21 at 14:30
    
When the denominator is divisible by $3$ distinct primes primes, you can find $6$ and $8$ numerators that yield the same value, but still no examples of a value reached by exactly an odd number of numerators, other than $1$... –  Thomas Andrews Jul 21 at 14:37

3 Answers 3

Given $n$, let $a$ and $b$ be integers coprime with $n$. Then:

$$\sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k=1}^n k \left\{ \frac{bk}{n}\right\}$$

As Michael Stocker commented:

$$f(a,n) = \sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k=1}^n k \frac{ak \mod n}{n} = \frac{1}{n}\sum_{k=1}^n k (ak \mod n)$$ $$f(b,n) = \sum_{k=1}^n k \left\{ \frac{bk}{n}\right\} = \sum_{k=1}^n k \frac{bk \mod n}{n} = \frac{1}{n}\sum_{k=1}^n k (bk \mod n)$$

I've been able to prove that, as Thomas Andrews said, if $ab \equiv 1 \pmod{n}$ then $f(a,n) = f(b,n)$:

Let $k' := ak \mod n$ then $k' (bk' \mod n) = k (ak \mod n)$. Here's the proof: $k'[b(ak \mod n) \mod n] = k'(abk \mod n) = k'(k \mod n) = k'k = k(ak \mod n)$.

Note that $\lbrace (ak \mod n) \vert 1\leq k \leq n\rbrace = \lbrace 0, 1,2\cdots ,n-1\rbrace$.

So now $$f(a,n) = \sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k'=1}^n k' \left\{ \frac{bk'}{n}\right\} = f(b,n)$$

Now for the cases like $f(8,65) = f(18,65)$ where $ab \not\equiv 1$ I've found that $$k(ak \mod n) - k(bk\mod n) = \\(n-k)(b(n-k)\mod n) - (n-k)(b(n-k)\mod n)$$

But so far I've been unable to caracterize the pairs $(a,b)$ with that property.

share|improve this answer
    
But doesn't the first sum become $\sum_{k=1}^n k \left\{ \frac{bk'}{n}\right\}$ instead of $\sum_{k=1}^n k \left\{ \frac{bk}{n}\right\}$? –  N. S. Jul 21 at 13:31
    
@N.S. It will become $\sum_{k'=1}^n k' \left\{\frac{bk'}{n}\right\}$ wich is equivalent... I think –  Darth Geek Jul 21 at 13:34
    
No it doesn't. As you said, for each $k$ there exists a $k'$ so that $\left\{ \frac{ak}{n} \right\}= \left\{ \frac{bk'}{n} \right\}$. Which means that $k\left\{ \frac{ak}{n} \right\}$ becomes $k\left\{ \frac{bk'}{n} \right\}$.... –  N. S. Jul 21 at 13:43
    
@N.S. You are absolutely right. I'll try to think a way to fix this. –  Darth Geek Jul 21 at 14:06
    
@ThomasAndrews my proof is not right as pointed out in the comment. I'm trying to work out a fix. I think $a$ and $b$ must me coprime with $n$ but $a-b$ must not. –  Darth Geek Jul 21 at 16:53

Here is a small GNU Maxima script to ease experimentation


    display2d : false;

    /* x rational */
    my_floor(x) := block(
        if (x >= 0) then block(
            ab : divide(ratnumer(x),ratdenom(x)),
            a : ab[1], b : ab[2],
            if (b = 0) then block(
                return(x)
            ) else block(
                return(x - b/ratdenom(x))
            )
        ) else block(
            ab : divide(ratnumer(-x),ratdenom(-x)),
            a : ab[1], b : ab[2],
            if (b = 0) then block(
                return(x)
            ) else block(
                return(x - (1-b/ratdenom(-x)))
            )
        )
    );

    /* x rational */
    my_frac(x) := x - my_floor(x);

    cz : 0; cnz : 0;
    for N : 1 thru 20 do block(
    for m1 : 1 thru 20 do block(
    for m2 : m1+1 thru 20 do block(
        mylhs : apply("+",makelist(k*my_frac(m1*k/N),k,1,N)),
        myrhs : apply("+",makelist(k*my_frac(m2*k/N),k,1,N)),
        if (mylhs - myrhs = 0) then block(
            cz : cz+1,
            print(N,m1,m2,"|",mylhs)
        ) else block(
            cnz : cnz+1
        )
    )));
    print(cz,"|",cnz);

share|improve this answer
    
Using the script above, I have found no solutions with $1 \le N,m1,m2 \le 100$, $gcd(N,m1) \neq 1$, $gcd(N,m2) \neq 1$, $gcd(m1,m2) = 1$. –  andre Jul 21 at 15:22
    
What do you mean by "no solutions?" Do you mean no more solutions than the ones above? –  Thomas Andrews Jul 21 at 18:30
    
Exactly what I've said. I have found no solution for $1 \le N,m1,m2 \le 100$ with the additional conditions $gcd(N,m1) \neq 1$, $gcd(N,m2) \neq 1$ and $gcd(m1,m2) = 1$. You may substitute $m1=a$ and $m2=b$. –  andre Jul 21 at 19:00
    
Sorry, reading comprehension failure on my part - read $\neq$ as $=$... –  Thomas Andrews Jul 21 at 19:45
    
Because of my low reputation, I comment here. I believe we should identify the pattern of the function $f(n,m,k) := (n-m)/n - \{mk/N\} + \{m(k+1)/N\}$ in order to perform a summation by parts. –  andre Jul 22 at 22:41

[Raw data deleted.]

Defining $$f(a,n)=\sum_{k=1}^{n-1} k\left\{\frac{ka}{n}\right\}$$ it's pretty obvious that $f(a,n)+f(n-a,n)=\frac{n(n-1)}{2}$ when $(a,n)=1$. It's also true, as proven by Darth Geek, that if $ab\equiv 1\pmod n$ then $f(a,n)=f(b,n)$.

Further data leads to:

Conjecture: If $f(a,n)=f(b,n)$ then $n\mid (a-b)(ab-1)$, or, equivalently, $a+a^{-1}\equiv b+b^{-1}\pmod n$, where the inverses are taken modulo $n$.

This would mean that the pairs $a,a^{-1}$ are the only solutions when $n$ a prime.

It is definitely not sufficient, since $a=3,b=48,n=65$ satisfies this condition.

This conjecture holds for all integers $4\leq n\leq 5000$.

$$\begin{align}f(a,n)&=\frac{a}{n}\sum_{k=1}^{n-1} k^2 - \sum_{k=1}^{n-1} k\left\lfloor\frac{ka}{n}\right\rfloor\\ &=\frac{a(n-1)(2n-1)}{6} - \sum_{k=1}^{n-1} k\left\lfloor\frac{ka}{n}\right\rfloor \end{align}$$

Thus $f(a,n)$ is an integer if $(n,6)=1$.

share|improve this answer
    
Perhaps the condition is sufficient for prime $n$? It's just a guess since for prime $n$ the sum may behave nicer. –  barto Jul 22 at 10:57
    
For prime $n$, that means $ab=1$ or $a=b$, and that does appear to be sufficient in that case, with the data I'm looking at. @barto –  Thomas Andrews Jul 22 at 12:16
    
Thank you, that's interesting. Understanding the behavior for prime $n$ would be a good step forward. –  barto Jul 22 at 18:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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