If $A$ is regular, is the language $\{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$ regular? Here is the question:

Let $A$ be any regular set over some alphabet $\Sigma$. Is the language
  $$
L = \{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}
$$
  necessarily regular?

I am unable to approach this question to prove whether it is regular or not.
In fact, this seems like a difficult question.
Unlike with other regular language problems, it does not seem intuitively clear whether or not the statement is true.
 A: To my knowledge, the best answer to this (type of) problem was given in [1]. Here is a sketch of this proof. I will use freely the notation
$u^{-1}L = \{v \in A^* \mid uv \in L\}$.
Proof. Let $K$ be a regular language of $A^*$ and let $\mathcal{A} = (Q, A, q_0, F)$ be its minimal DFA. For each state $q \in Q$, consider the regular languages 
$$
\text{$L_q = \{x \in A^* \mid q_0  x = q\}$ and $R_q = \{y \in A^* \mid q  y \in F\}$.}
$$
Observe that if $x \in L_q$, then 
$$
  R_q = \{y \in A^* \mid q_0xy \in F\} = \{y \in A^* \mid xy \in K\} 
      = x^{-1}K \qquad (1)
$$
We are interested in the language
\begin{align}
  M &= \{ x \in A^* \mid \text{there exists $y \in A^*$ such that $|y| = |x|^2$ and  $xy \in K$} \} \\
  &= \{ x \in A^* \mid xA^{|x|^2} \cap K \not= \emptyset\} \\
  &= \{ x \in A^* \mid A^{|x|^2} \cap x^{-1}K \not= \emptyset\}
\end{align}
Since $A^* = \bigcup_{q \in Q} L_q$, it suffices to prove that, for each $q \in Q$, $M \cap L_q$ is regular. Now by (1), we get
\begin{align}
  M \cap L_q &= \{ x \in L_q \mid A^{|x|^2} \cap x^{-1}K \not= \emptyset\} \\
  &= \{ x \in L_q \mid A^{|x|^2} \cap R_q \not= \emptyset\} \qquad (2)
\end{align}
At this point, one needs the fact that, for each regular set $R$ of $A^*$, the set $\{|u| \mid u \in R\}$ is an ultimately periodic subset of $\mathbb{N}$. (You can prove this as an exercise, or use the fact that rational subsets of monoids are closed under morphisms, if you know what it means). In particular, the set $N_q = \{|u| \mid u \in R_q\}$ is an ultimately periodic subset of  $\mathbb{N}$. Moreover, it follows from (2) that
$$
  M \cap L_q = \{ x \in L_q \mid |x|^2 \in N_q \}
$$
A little effort is still needed to show that if $S$ is an ultimately periodic subset of $\mathbb{N}$, then $\{n \in \mathbb{N} \mid n^2 \in S\}$ is also ultimately periodic. A similar property holds not only for $n^2$, but for many other functions of $n$, as shown in [1]. In particular $M_q = \{n \in \mathbb{N} \mid n^2 \in N_q\}$ is ultimately periodic and we get
$$
  M \cap L_q = \{ x \in L_q \mid |x| \in M_q \}
$$
It follows that $M \cap L_q$ is regular, which concludes the proof.
[1] J. I. Seiferas and R. McNaughton, Regularity-preserving relations, Theoret. Comput. Sci. 2 (1976), no. 2, 147--154.
