I'm trying to prove the if $𝑀$ is a $𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most $𝑘^3$. first I have to prove that if a string syncs two states, then its length is at most $k^2$.
The question was answered here.
The proof of this a standard shrinking argument: if such a word is longer than $𝑘^2$, then during the runs from $𝑞_1,𝑞_2$, a pair of states repeats, and we can shrink $𝑤$.
But how to know if the repeating string in both paths from $𝑞_1,𝑞_2$ to some states like $q_i$ is the same? and shrinking the string won't damage the synchronization?
To make it more clear I drew the below picture.
The string $abcd$ takes $𝑞_1,𝑞_2$ to $q_i$ but after eliminating the loops, string $acd$ takes $𝑞_1$ to $q_i$ and string $abd$ takes $𝑞_2$ to $q_i$, thus removing the loops will break the synchronization.
Any suggestions would be greatly appreciated, thanks.
Edit: This is the visualisation I drew from Hendrik Jan's helpful answer:
Consider two arbitrary states $q_1$ and $q_2$ where $𝛿(q_1, w)=𝛿(q_2, w)=q_i$.
Suppose $|w|=k,\ w=v_1…v_k$ then: The loop happens when $𝛿((q_1^j, q_2^j),\ v_{j+1})=(q_1^i, q_2^i)$.