Some Chassidim have the custom to leave letters at the graves of deceased Rebbes. Is it mutar to send a letter to any deceased Rebbe (specifically the Lubavitcher Rebbe), or is this similar to Avodah Zarah?
The Torah forbids various superstitious and idolatrous activities including "doresh el hametim":
וְחֹבֵר, חָבֶר; וְשֹׁאֵל אוֹב וְיִדְּעֹנִי, וְדֹרֵשׁ אֶל-הַמֵּתִים
or a charmer, or one that consulteth a ghost or a familiar spirit, or a consulter of the dead. (Deut. 18:11)
If one intends for the Rebbe to respond with a message, such as the practice of flipping through a book, and hoping that the dead will guide one's hand, that would perhaps violate this according to Rambam's definition of it in Hilkhot Avodah Zarah (11:14). See here.
If the fax is a request that the Rebbe assist you, or even that he ask God to help you, that would likely be forbidden as well. Indeed, regarding beseeching the dead, even that they act as intermediaries, this would likely be forbidden (possibly severely). Rambam writes in Hilkhot Evel (4:4):
ולא יפנה אדם לבקר הקברות
There are different textual variants of this line and different explanations of them, but R. Qafih explains that Rambam holds that one should not even go to a cemetery, lest one come to beseech the dead. Similarly, see Nefesh HaRav p. 254 that the Rav's family custom was to avoid graveyards to avoid the appearance of doresh el hametim.
In a similar vein, R. Moshe Tzuriel notes here that Rambam (Hilkhot Ta'aniyot 4:17) emphasises that prayers in a graveyard are not meant to be directed to the dead. In this, Rambam rules like Rabbi Levi Bar Hamma, in Ta'anit 16a against a contrary opinion recorded there. R. Tzuriel (there) is of the opinion that those who were accustomed to pray in various forms to the dead are following the contrary view in Ta'anit, but that halakha is not in accordance with that view.
Additionally, Maharam Shikk writes in a responsum (OH 293) that such practices raise both the issue of dresh el hametim, and of serving God through an intermediary (apparently the prohibition of avoda zara). He concludes that if one relates one's problems to the dead hoping that they will intercede with God it is permissible, but if one wants help from them directly, it would be forbidden. He emphasises that even using them as intermediaries is forbidden according to many authorities.
Similarly, the Ben Ish Hai writes in a responsum (Rav P'alim Vol II YD 31) that it is forbidden to make requests of a dead person directly. Doing so constitutes doresh el hametim. One may only ask that the dead intercede with God. He writes this in explanation of the Zohar (Acharei Mot: 71) which is quoted by some as a source to permit praying to the dead:
נמצא לא הותר לאדם להתפלל על קברי הצדיקים, לשאול בקשתו מן הצדיקים עצמן, כי זה חשיב דורש אל המתים, אלא הוא מתפלל ושואל בקשתו מהקב"ה, ורק מבקש מנפש הצדיק שתתפלל עליו לפני הקדוש ברוך הוא, שישמע תפלתו ויעשה בקשתו
Others, take an even harsher stance. The Bach (YD 217:51) implies that prayer in a cemetery can only be permitted if it is addressed to God; not the dead. (although he cites views that even this would be prohibited, see there for more):
ודוקא להשתטח על קברי אבות ולהתפלל לפניו יתברך
Additionally, the Hokhmat Adam (Issur V'heter 89:7) writes negatively about people who discuss their problems with the dead:
ז איסור דורש אל המתים זה שמרעיב עצמו ולן בבית הקברות כדי שתשרה עליו רוח הטומאה (סימן קע"ט סעיף י"ג) ואותן נשים וכן עמי הארצות שהולכין על קברי מתים וכאילו מדברים עם המתים ואומרים להם צרותיהם קרוב הדבר שהם בכלל זה
And [regarding] those women and ignoramuses who go to graves and speak as though to the dead and tell them their woes, and it seems likely that they are included in this prohibition.[i] (My translation of the bolded portion)
Maharam Mintz (Responsa:79) similarly cites the opinion that making requests of the dead; even just that they intercede with God is forbidden as doresh el hametim:
כי בלאו הכי יש גדולים קראו תגר ע"ד זה וקראו ודורש אל המתים, דרוב עמי הארץ ונשים עבידי מליצים בינם ובין קונם ב"ה.
The Minhagei Maharil (Hilkhot Ta'anit 18), quoted by the Elya Rabba (581), Ba'er Hetev (OH 581:17), and the Mishna Berurah (581:27) similarly writes that one shouldn't address the dead at all:
והמשתטח על קברי הצדיקים ומתפלל אל ישים מגמתו נגד המתים השוכבים שם, אך יבקש מאת השם יתברך שיתן אליו רחמים בזכות הצדיקים שוכני עפ
That is, one mustn't address the dead or even pay attention to them, but only address God.
The Hayei Adam (138:5), and Kitzur (128:13) paraphrase the Maharil and add that addressing the dead directly would seem to violate doresh el hametim:
ויעשה הקדוש ברוך בו חסד בזכות הצדיקים אבל אל ישים מגמתו נגד המתים השוכנים שם, כי קרוב הדבר שיהיה בכלל ודורש אל המתים
[i] At face value this seems quite strange, since this seems quite different from the classical descriptions, and indeed his own description of doresh el hemetim. Perhaps he means that it is similarly forbidden, but for a different reason; i.e. avodah zara, although this is admittedly difficult to read into his words.
The Minchas Yitzchak 8:53) was asked if one is allowed to write one's name and leave the paper on the grave of a Tzaddik (The Chasam Sofer, in that case).
He wrote that Bach and the Maharil forbid asking from the dead, but the Sefer Chassidim and the Zohar seem to permit, and the Maharam Shik is left undecided.
Moreover, he says that the same logic which permits asking a Tzaddik to pray for one (while alive) would apply after death - that all the Jews are one entity, and Haashem wouldn't want a Tzaddik to suffer from another person's pain. So since a Tzaddik feels another person's pain after (the Tzaddik's) death, he can remove suffering.
So the Maharam Shik says that since opinions allow, and others forbid, one should rather do "nothing" and not go.
But the Minchas Elazar (1:68) argues, and says that it's a Mitzvah to pray by a Tzaddik's grave.
He quotes a few Gemaras which mention that the Tanayim and Amoraim (as well as the Arizal and his students) would talk to dead people by their graves, which would imply that it's permitted.
He says that "Doresh El HaMeisim" is only when one goes to live in a cemetery and wants their "spirit of impurity" to rest on him.
However, if one wants their "spirit of purity", or to inform them of his pain, it's permitted.
Moreover, he says that it's unlikely that the Maharil would argue on all those Gemaras. Rather, the Maharil must hold that one shouldn't pray to the Tzaddik (like the famous debate about whether it's permitted to say Machnisei Rachamim). However, as "we" hold that one can say Machnisei Rachamim, all the more so can one pray to a Tzaddik.
And since there's no sin, one should go and meditate on one's day of death and have the righteous pray on one's behalf.
So the Minchas Yitzchak wrote that if one is allowed to ask of departed Tzaddikim, one is allowed to write them Kvitlach.
But he says that there were Poskim (such as the Satmar Rov) who were against going to graves, and only big Tzaddikim should go.
Therefore, he said that both sides have a point.
Yes, it is permissible and is in fact an ancient custom extending all the way back to Calev separating from the spies when they entered the land of Israel to stop at the graves of the Avot to pray that they seek mercy from G-d on his behalf because of their intentions. The written petition serves the same function as saying the words aloud as both are putting the words of ones prayer into an action.
sota 34b "Rava said: this teaches that Calev disassociated from the plans of the spies and went and protrated himself at the graves of the forefathers.He said to them my fathers, ask for mercy upon me, that I may be saved from the plans of the spies"
אמר רבא מלמד שפירש כלב מעצת מרגלים והלך ונשתטח על קברי אבות אמר להן אבותי בקשו עלי רחמים שאנצל מעצת מרגלים
And Tosaphot to this quote from Sotah emphasizes:
אבותי בקשו עלי רחמים - וא"ת והאמר בפרק מי שמתו (ברכות דף יח.) דמיתי לא ידעין מידי ומשמע במסקנא. ואפילו אבות העולם יש לומר דעל ידי תפלה שזה מתפלל מודיעין להן שכך נתפלל והכי אמר בפרק שני דתענית (דף טז.) למה יוצאין לבית הקברות כדי שיבקשו עליהם מתים רחמים וכן בפרקי דחסידים בעובדא דרבי מנא דאשתטח אמערתא דאבוה:
Taanis 16a "Why do we go out to the cemetery? Rebbi Levi bar Chama and Rebbi Chanina argue on this, one says we are considered before you as dead bodies. And one says so that the deceased should beg for mercy on our behalf."
למה יוצאין לבית הקברות פליגי בה ר' לוי בר חמא ור' חנינא חד אמר הרי אנו חשובין לפניך כמתים וחד אמר כדי שיבקשו עלינו מתים רחמים מאי בינייהו איכא בינייהו קברי עכו"ם
And again, Tosafot adds that this is a practice in all Jewish communities:
יוצאין לבית הקברות. מכאן נוהגין בכל מקום לילך לבית הקברות בט' באב שהרי ט"ב הוי תענית צבור כמו שהיו עושין מפני הגשמים:
And the Maharsha in Chiddushei Aggadot adds that the Tzaddikim laying there will seek mercy on your behalf.
וחד אמר כדי שיבקשו עלינו מתים כו'. והכי איתא במדרש שאבות מבקשים רחמים עלינו:
kitzur shulchan aruch ch. 128 paragraph 13 " It is customary to go to the cemetary after the morning service on the day preceeding Rosh haShana and to pray at the graves of the rightous. We give charity o the poor & recite many supplications to arouse the holy rightous who are burried there to intercede on our behalf on the day of judgement. Furthermore, since tzadikim are burried there, the place is holy and pure, and prayers recited there are received more favorably b/c they were recited on holy ground."
נוֹהֲגִין לֵילֵךְ בְּעֶרֶב רֹאשׁ הַשָּׁנָה אַחַר תְּפִלַּת שַׁחֲרִית לְבֵית הַקְּבָרוֹת לְהִשְׁתַּטֵּחַ עַל קִבְרֵי הַצַּדִּיקִים, וְנוֹתְנִים שָׁם צְדָקָה לַעֲנִיִּים, וּמַרְבִּים תַּחֲנוּנִים לְעוֹרֵר אֶת הַצַּדִּיקִים הַקְּדוֹשִׁים אֲשֶׁר בָּאָרֶץ הֵמָּה, שֶׁיַּמְלִיצוּ טוֹב בַּעֲדֵנוּ בְּיוֹם הַדִּין. וְגַם מֵחֲמַת שֶׁהוּא מְקוֹם קְבוּרַת הַצַּדִּיקִים, הַמָּקוֹם הוּא קָדוֹשׁ וְטָהוֹר, וְהַתְּפִלָּה מְקֻבֶּלֶת שָׁם בְּיוֹתֵר, בִּהְיוֹתָהּ עַל אַדְמַת קֹדֶשׁ, וְיַעֲשֶׂה הַקָּדוֹשׁ בָּרוּךְ הוּא חֶסֶד בִּזְכוּת הַצַּדִּיקִים. אֲבָל אַל יָשִׂים מֲגָמָתוֹ נֶגֶד הַמֵּתִים הַשּׁוֹכְנִים שָׁם, כִּי קָרוֹב הַדָּבָר שֶׁיִּהְיֶה בִּכְלָל וְדוֹרֵשׁ אֶל הַמֵּתִים. אַךְ יְבַקֵּשׁ מֵהַשֵּׁם, יִתְבָּרַךְ שְׁמוֹ, שֶׁיְרַחֵם עָלָיו בִּזְכוּת הַצַּדִּיקִים שׁוֹכְנֵי עָפָר (תקפא).
Bava Basra 116a " Rebbi Pinchas bar Chama explained, whoever has a sick person in his house should go to a sage and have them plead for mercy on his behalf. For it says, "A king's fury, messengers of death, but a wise man will wipe it away"."
דרש ר' פנחס בר חמא כל שיש לו חולה בתוך ביתו ילך אצל חכם ויבקש עליו רחמים שנא' (משלי טז, יד) חמת מלך מלאכי מות ואיש חכם יכפרנה:
A Jew is permitted t o ask another Jew to pray on our behalf as noted by the fact we have tradition of saying tehillim on behalf of the sick and a special prayer during the reading of the Torah. This also extends to someone who has passed away but specifically a tzadik as many sources in both the talmud and kabalah note that tzadikim after they pass away are still concerned with their children, students, and those who they are close with. During the Rebbe's lifetime he received letters from people of all walks of life for advise and for requests that he pray on their behalf. As the Zohar says, a tzadik is found more so in all of the worlds after his passing than during his lifetime which means that the guidance and blessings and prayers to Hashem on our behalf are not interrupted after their passing.